caa a22 4500 445805439 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-011-9487-4 doi (NATIONALLICENCE)springer-10.1007/s00453-011-9487-4 Editing Graphs into Disjoint Unions of Dense Clusters [Elektronische Daten] [Jiong Guo, Iyad Kanj, Christian Komusiewicz, Johannes Uhlmann] In the Π-Cluster Editing problem, one is given an undirected graphG, a density measureΠ, and an integerk≥0, and needs to decide whether it is possible to transformG by editing (deleting and inserting) at mostk edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected componentK=(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 mosts 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), wheres 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 parameterk for0<μ<1. Springer Science+Business Media, LLC, 2011 Cluster Editing nationallicence Parameterized complexity nationallicence Data reduction nationallicence Forbidden subgraph characterization nationallicence NP-hardness nationallicence Clique relaxations nationallicence Guo Jiong Universität des Saarlandes, Campus E 1.7, 66123, Saarbrücken, Germany aut Kanj Iyad School of Computing, DePaul University, 243. S. Wabash Avenue, 60604, Chicago, IL, USA aut Komusiewicz Christian Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743, Jena, Germany aut Uhlmann Johannes Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743, Jena, Germany aut Algorithmica Springer-Verlag 61/4(2011-12-01), 949-970 0178-4617 61:4<949 2011 61 453 https://doi.org/10.1007/s00453-011-9487-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9487-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Guo Jiong Universität des Saarlandes, Campus E 1.7, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Kanj Iyad School of Computing, DePaul University, 243. S. Wabash Avenue, 60604, Chicago, IL, USA aut NATIONALLICENCE 700 1- Komusiewicz Christian Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743, Jena, Germany aut NATIONALLICENCE 700 1- Uhlmann Johannes Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743, Jena, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 949-970 0178-4617 61:4<949 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer