License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.6
URN: urn:nbn:de:0030-drops-80728
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8072/
Bliznets, Ivan ;
Karpov, Nikolai
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Abstract
Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model generally clusters are defined as cliques. However, such approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different types of cliques relaxations often considered as clusters.
In our work, we consider a problem of partitioning graph into clusters and a problem of isolating cluster of a special type where by cluster we mean highly connected subgraph. Initially, such clusterization was proposed by Hartuv and Shamir. And their HCS clustering algorithm was extensively applied in practice. It was used to cluster cDNA fingerprints, to find complexes in protein-protein interaction data, to group protein sequences hierarchically into superfamily and family clusters, to find families of regulatory RNA structures. The HCS algorithm partitions graph in highly connected subgraphs. However, it is achieved by deletion of not necessarily the minimum number of edges. In our work, we try to minimize the number of edge deletions. We consider problems from the parameterized point of view where the main parameter is a number of allowed edge deletions. The presented algorithms significantly improve previous known running times for the Highly Connected Deletion (improved from \cOs\left(81^k\right) to \cOs\left(3^k\right)), Isolated Highly Connected Subgraph (from \cOs(4^k) to \cOs\left(k^{\cO\left(k^{\sfrac{2}{3}}\right)}\right) ), Seeded Highly Connected Edge Deletion (from \cOs\left(16^{k^{\sfrac{3}{4}}}\right) to \cOs\left(k^{\sqrt{k}}\right)) problems. Furthermore, we present a subexponential algorithm for Highly Connected Deletion problem if the number of clusters is bounded. Overall our work contains three subexponential algorithms which is unusual as very recently there were known very few problems admitting subexponential algorithms.
BibTeX - Entry
@InProceedings{bliznets_et_al:LIPIcs:2017:8072,
author = {Ivan Bliznets and Nikolai Karpov},
title = {{Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {6:1--6:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8072},
URN = {urn:nbn:de:0030-drops-80728},
doi = {10.4230/LIPIcs.MFCS.2017.6},
annote = {Keywords: clustering, parameterized complexity, highly connected}
}
|
Keywords: |
|
clustering, parameterized complexity, highly connected |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
