# (1,1)-Cluster Editing is Polynomial-time Solvable

arXiv: https://arxiv.org/abs/2210.07722 · HTML: https://mlsanity.com/paper/2210.07722/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 16 references that are in the map.
- First posted on arXiv 14 Oct 2022.

## Builds on (most cited first, 1 of 1)

- [On the Complexity of Multi-Parameterized Cluster Editing](https://mlsanity.com/paper/1511.09360/) (2015)

## Abstract (arXiv)

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)rightarrow 0,1,dots, a and d^*: V(G)rightarrow 0,1,dots, 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.