Papers › (1,1)-Cluster Editing is Polynomial-time Solvable
(1,1)-Cluster Editing is Polynomial-time Solvable
Gregory Gutin, Anders Yeo
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 C₃-free and C₄-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving (1,1)-{Cluster Editing} on C₃-free and C₄-free graphs of maximum degree at most 3.
Code
No code repository is listed for this paper in the archive or in Syntology's graph.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
| Task | Dataset | Model | Metric | Value | Rank at snapshot | Leaderboard | Report |
|---|---|---|---|---|---|---|---|
| BIG-bench Machine Learning | 38-Cloud | Fb232 | account and password | 100 | #1 of 1 | Archive leaderboard | report |
Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections