Editing Graphs into Disjoint Unions of Dense Clusters

Editing Graphs into Disjoint Unions of Dense Clusters

0.00 Avg rating0 Votes
Article ID: iaor201110815
Volume: 61
Issue: 4
Start Page Number: 949
End Page Number: 970
Publication Date: Dec 2011
Journal: Algorithmica
Authors: , , ,
Keywords: decision theory
Abstract:

In the Π‐Cluster Editing problem, one is given an undirected graph G, a density measure Π, and an integer k≥0, and needs to decide whether it is possible to transform G by editing (deleting and inserting) at most k edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected component K=(V K ,E K ) satisfies Π. The well‐studied Cluster Editing problem is a special case of this problem with Π≔‘being a clique’. In this work, we consider three other density measures that generalize cliques: (1) having at most s missing edges (s‐defective cliques), (2) having average degree at least |V K |-s (average‐s‐plexes), and (3) having average degree at least μ·(|V K |-1) (μ‐cliques), where s and μ are a fixed integer and a fixed rational number, respectively. We first show that the Π‐Cluster Editing problem is NP‐complete for all three density measures. Then, we study the fixed‐parameter tractability of the three clustering problems, showing that the first two problems are fixed‐parameter tractable with respect to the parameter (s,k) and that the third problem is W[1]‐hard with respect to the parameter k for 0<μ<1.

Reviews

Required fields are marked *. Your email address will not be published.