pipette
ESEspañol

Parameterizing Cluster Editing by the Number of Deletions

Vincent Froese, Leon Kellerhals, Frank Sommer, Manuel Sorge, Ond\v{r}ej Such\'y

Preprint

In the authors' words

In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn 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 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 edits, at most of which are deletions, is W[1]-hard with respect to , even when combined with the pathwidth and the feedback edge set number of the input graph. The hardness extends to editing towards -free graphs for every graph 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 is combined with the excess of 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 -time algorithm and a problem kernel with vertices. Both results extend to packings of stars and the algorithm extends to -free editing.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.