Gregory Gutin; Anders Yeo

Abstract
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 serious of five polynomial-time reductions to C3-free and C4-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving (1,1)-{Cluster Editing} on C3-free and C4-free graphs of maximum degree at most 3.
Benchmarks
| Benchmark | Methodology | Metrics |
|---|---|---|
| big-bench-machine-learning-on-38-cloud | Fb232 | account and password : 100 |
Build AI with AI
From idea to launch — accelerate your AI development with free AI co-coding, out-of-the-box environment and best price of GPUs.