Parameterizing Cluster Editing by the Number of Deletions
Overview & Synopsis
In Cluster Editing, we are given a graph $G$ and an integer $k$ and ask whether at most $k$ edge insertions and deletions turn $G$ into a disjoint union of cliques. Komusiewicz and Niedermeier asked in 2012 at MFCS whether Cluster Editing is fixed-parameter tractable with respect to the number $\ell$ of edge deletions, a parameter based on the solution rather than on the structure of the input graph. We answer this question negatively: Cluster Editing with at most $k$ edits, at most $\ell$ of which are deletions, is W[1]-hard with respect to $\ell$, even when combined with the pathwidth and the feedback edge set number of the input graph. The hardness extends to editing towards $H$-free graphs for every graph $H$ that is a clique minus one edge on at least four vertices. On the positive side, we show that the problem becomes fixed-parameter tractable when $\ell$ is combined with the excess $μ$ of $k$ over the lower bound given by a packing of modification-disjoint induced paths on three vertices, a lower bound that state-of-the-art solvers use. Each of the two parameters alone leads to intractability, but together they admit an $O(4^{μ+\ell}\cdot(n+m+μ))$-time algorithm and a problem kernel with $O((\ell+μ)^2)$ vertices. Both results extend to packings of stars and the algorithm extends to $H$-free editing.
arxiv.org)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Parameterizing Cluster Editing by the Number of Deletions |
|---|---|
| Author / Organization | Vincent Froese, Leon Kellerhals, Frank Sommer, Manuel Sorge, Ondřej Suchý |
| Subject & Discipline | cs.DS |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-271509 |
| Original Source Link | Visit Source Page on arxiv.org » |