(1,1)-Cluster Editing is polynomial-time solvable

A graph H is a clique graph if H is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the ( a , d ) -Cluster Editing problem, where for fixed natural numbers a , d , given a graph G and vertex-weights a ∗ : V ( G ) → { 0 , 1 , … , a } and d ∗ : V ( G ) → { 0 , 1 , … , d } , we are to decide whether G can be turned into a cluster graph by deleting at most d ∗ ( v ) edges incident to every v ∈ V ( G ) and adding at most a ∗ ( v ) edges incident to every v ∈ V ( G ) . Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of ( a , d ) -Cluster Editing for all pairs a , d apart from a = d = 1 . Abu-Khzam (2017) conjectured that ( 1 , 1 ) -Cluster Editing is in P. We resolve Abu-Khzam’s conjecture in affirmative by (i) providing a series of five polynomial-time reductions to C 3 -free and C 4 -free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving ( 1 , 1 ) -Cluster Editing on C 3 -free and C 4 -free graphs of maximum degree at most 3.