Cluster editing with locally bounded modifications ?
Given an undirected graphG=(V,E) G = ( V , E ) and a nonnegative integerk k , the NP-hard Cluster Editing problem asks whetherG G can be transformed into a disjoint union of cliques by modifying at mostk k edges. In this work, we study how local degree bounds influence the complexity ofCluster Editing and of the relatedCluster Deletion problem which allows only edge deletions. We show that even for graphs with constant maximum degreeCluster Editing andCluster 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 bothCluster Editing andCluster Deletion cannot be solved within a running time that is subexponential ink k ,|V| | V | , or|E| | E | . Finally, we present a problem kernelization for the combined parameter numberd d of clusters and maximum numbert t of modifications incident with a vertex thus showing thatCluster Editing andCluster Deletion become easier in case the number of clusters is upper-bounded.
graph modification problems parameterized algorithmics exponential-time hypothesis data reduction