Editing Graphs into Disjoint Unions of Dense Clusters |
| |
Authors: | Jiong Guo Iyad A Kanj Christian Komusiewicz Johannes Uhlmann |
| |
Affiliation: | 1.Universit?t des Saarlandes,Saarbrücken,Germany;2.School of Computing,DePaul University,Chicago,USA;3.Institut für Informatik,Friedrich-Schiller-Universit?t Jena,Jena,Germany |
| |
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 W1]-hard with respect to the parameter k for 0<μ<1. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|