Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorKratsch, Stefan
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorPilipczuk, Michal Pawel
dc.contributor.authorVillanger, Yngve
dc.PublishedLeibniz International Proceedings in Informatics 2013, 20:32-43eng
dc.description.abstractIn 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.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-ND 3.0eng
dc.subjectParameterized complexityeng
dc.subjectcluster editingeng
dc.subjectcorrelation clusteringeng
dc.subjectsubexponential algorithmseng
dc.subjecttight boundseng
dc.titleTight bounds for parameterized complexity of Cluster Editingen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright F.V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villangeren_US
dc.subject.nsiVDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Matematisk modellering og numeriske metoder: 427
dc.subject.nsiVDP::Mathematics and natural scienses: 400::Information and communication science: 420::Mathematic modelling and numerical methods: 427
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY-ND 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY-ND 3.0