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 (BenDor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APXhard (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 nvertex 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 = {3243},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3920},
URN = {urn:nbn:de:0030drops39209},
doi = {10.4230/LIPIcs.STACS.2013.32},
annote = {Keywords: parameterized complexity, cluster editing, correlation clustering, subexponential algorithms, tight bounds}
}
2013
Keywords: 

parameterized complexity, cluster editing, correlation clustering, subexponential algorithms, tight bounds 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

2013 