Subexponential algorithm for d-cluster edge deletion: Exception or rule?
| Autor: | Fahad Panolan, Saket Saurabh, Neeldhara Misra |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Optimization problem
Computer science Computer Networks and Communications Correlation clustering 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics 020204 information systems Cluster (physics) 0202 electrical engineering electronic engineering information engineering Computer Science & Automation Mathematics Discrete mathematics 021103 operations research Exponential time hypothesis Graph theoretic Applied Mathematics Graph Data point Computational Theory and Mathematics 010201 computation theory & mathematics Adjacency list Algorithm |
| Zdroj: | Lecture Notes in Computer Science Mathematical Foundations of Computer Science 2013 ISBN: 9783642403125 MFCS |
| ISSN: | 0022-0000 |
| Popis: | The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually ``not too far apart'', without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm STACS, 2013]. That is, there is no algorithm solving the problem in time 2 degrees((k))n(O(1)). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time O(2(O(root dk)) + m + n). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2 degrees((k))n(O(1)). We show, further, that even the problem of deleting edges to obtain a graph with d s-clubs cannot be solved in time 2 degrees((k))n(O)(1) for any fixed s, d >= 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect