dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Kratsch, Stefan | |
dc.contributor.author | Pilipczuk, Marcin | |
dc.contributor.author | Pilipczuk, Michal Pawel | |
dc.contributor.author | Villanger, Yngve | |
dc.date.accessioned | 2016-05-31T08:19:22Z | |
dc.date.available | 2016-05-31T08:19:22Z | |
dc.date.issued | 2013 | |
dc.identifier.isbn | 978-3-939897-50-7 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/1956/12041 | |
dc.description.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. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY-ND 3.0 | eng |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/3.0/ | eng |
dc.subject | Parameterized complexity | eng |
dc.subject | cluster editing | eng |
dc.subject | correlation clustering | eng |
dc.subject | subexponential algorithms | eng |
dc.subject | tight bounds | eng |
dc.title | Tight bounds for parameterized complexity of Cluster Editing | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2016-04-07T06:46:05Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright F.V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.stacs.2013.32 | |
dc.identifier.cristin | 1069657 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 32-43 | |
dc.subject.nsi | VDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Matematisk modellering og numeriske metoder: 427 | |
dc.subject.nsi | VDP::Mathematics and natural scienses: 400::Information and communication science: 420::Mathematic modelling and numerical methods: 427 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2013, 20:32-43 | |
dc.source.volume | 20 | |