Cluster editing with locally bounded modifications

https://doi.org/10.1016/j.dam.2012.05.019Get rights and content
Under an Elsevier user license
open archive

Abstract

Given an undirected graph G=(V,E) and a nonnegative integer k, the NP-hard Cluster Editing problem asks whether G can be transformed into a disjoint union of cliques by modifying at most k edges. In this work, we study how “local degree bounds” influence the complexity of Cluster Editing and of the related Cluster Deletion problem which allows only edge deletions. We show that even for graphs with constant maximum degree Cluster Editing and Cluster Deletion are NP-hard and that this implies NP-hardness even if every vertex is incident with only a constant number of edge modifications. We further show that under some complexity-theoretic assumptions both Cluster Editing and Cluster Deletion cannot be solved within a running time that is subexponential in k|V|, or |E|. Finally, we present a problem kernelization for the combined parameter “number d of clusters and maximum number t of modifications incident with a vertex” thus showing that Cluster Editing and Cluster Deletion become easier in case the number of clusters is upper-bounded.

Keywords

Graph modification problems
Parameterized algorithmics
Exponential-time hypothesis
Data reduction

Cited by (0)

An extended abstract containing some of the results from this work as well as further fixed-parameter tractability results for Cluster Editing and Cluster Deletion appeared under the title “Alternative Parameterizations for Cluster Editing” in the proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011) (Komusiewicz and Uhlmann, 2011 [18]). The results of this work are also contained in the first author’s dissertation (Komusiewicz, 2011 [17]).