License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.32
URN: urn:nbn:de:0030-drops-39209
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3920/
Fomin, Fedor V. ;
Kratsch, Stefan ;
Pilipczuk, Marcin ;
Pilipczuk, Michal ;
Villanger, Yngve
Tight bounds for Parameterized Complexity of Cluster Editing
Abstract
In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, that is, by adding or deleting at most k edges. The motivation of the problem stems from various tasks in computational biology (Ben-Dor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APX-hard (Charikar et al., FOCS 2003), the version of the problem where the number of cliques may not exceed a prescribed constant p admits a PTAS (Giotis and Guruswami, SODA 2006).
We study the parameterized complexity of Correlation Clustering with this restriction on the number of cliques to be created. We give an algorithm that - in time O(2^{O(sqrt{pk})} + n+m) decides whether a graph G on n vertices and m edges can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies.
We complement these algorithmic findings by the following, surprisingly tight lower bound on the asymptotic behavior of our algorithm. We show that unless the Exponential Time Hypothesis (ETH) fails - for any constant 0 <= sigma <= 1, there is p = Theta(k^sigma) such that there is no algorithm deciding in time 2^{o(sqrt{pk})} n^{O(1)} whether an n-vertex graph G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies.
Thus, our upper and lower bounds provide an asymptotically tight analysis of the multivariate parameterized complexity of the problem for the whole range of values of p from constant to a linear function of k.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2013:3920,
author = {Fedor V. Fomin and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Yngve Villanger},
title = {{Tight bounds for Parameterized Complexity of Cluster Editing}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {32--43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-50-7},
ISSN = {1868-8969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3920},
URN = {urn:nbn:de:0030-drops-39209},
doi = {10.4230/LIPIcs.STACS.2013.32},
annote = {Keywords: parameterized complexity, cluster editing, correlation clustering, subexponential algorithms, tight bounds}
}
|
Keywords: |
|
parameterized complexity, cluster editing, correlation clustering, subexponential algorithms, tight bounds |
|
Collection: |
|
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
26.02.2013 |
