(1,1)-Cluster Editing ist in Polynomialzeit lösbar.

Ein Graph $H$ ist ein Cliquengraph, wenn $H$ eine knotendisjunkte Vereinigung von Cliquen ist. Abu-Khzam (2017) stellte das Problem der $(a,d)$-{Cluster-Bearbeitung} vor, bei dem für feste natürliche Zahlen $a,d$ gegeben ist, ob ein Graph $G$ und Knotengewichte $a^:\ V(G)\rightarrow {0,1,\dots, a}$ sowie $d^:\ V(G)\rightarrow {0,1,\dots, d}$ so modifiziert werden können, dass aus $G$ ein Clustergraph wird, indem man höchstens $d^(v)$ Kanten löscht, die mit jedem Knoten $v\in V(G)$ inzident sind, und höchstens $a^(v)$ Kanten hinzufügt, die mit jedem Knoten $v\in V(G)$ inzident sind. Ergebnisse von Komusiewicz und Uhlmann (2012) sowie Abu-Khzam (2017) boten eine Dichotomie der Komplexität (in P oder NP-vollständig) des Problems der $(a,d)$-{Cluster-Bearbeitung} für alle Paare $(a,d)$ außer $(a=d=1)$. Abu-Khzam (2017) vermutete, dass das Problem der $(1,1)$-{Cluster-Bearbeitung} in P liegt. Wir bestätigen Abu-Khzams Vermutung positiv durch (i) eine Reihe von fünf polynomiellen Reduktionen auf Graphen ohne Dreiecke ($C_3$-frei) und Vierecke ($C_4$-frei), deren maximale Knotengradzahl 3 nicht überschreitet, und (ii) die Entwicklung eines polynomiellen Algorithmus zur Lösung des Problems der $(1,1)$-{Cluster-Bearbeitung} auf solchen Graphen.