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.
Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.
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