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.IPEC.2019.18
URN: urn:nbn:de:0030-drops-114796
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11479/
Go to the corresponding LIPIcs Volume Portal

Golovach, Petr A. ; Thilikos, Dimitrios M.

Clustering to Given Connectivities

pdf-format:
LIPIcs-IPEC-2019-18.pdf (0.7 MB)

Abstract

We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and a sequence Lambda=<lambda_{1},...,lambda_{t}> of positive integers and we ask whether it is possible to remove at most k edges from G such that the resulting connected components are exactly t and their corresponding edge connectivities are lower-bounded by the numbers in Lambda. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k)* n^{O(1)}-step algorithm, for some function f that depends only on the parameter k. Our algorithm uses the recursive understanding technique that is especially adapted so to deal with the fact that we do not impose any restriction to the connectivity demands in Lambda.

BibTeX - Entry

@InProceedings{golovach_et_al:LIPIcs:2019:11479,
  author =	{Petr A. Golovach and Dimitrios M. Thilikos},
  title =	{{Clustering to Given Connectivities}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Bart M. P. Jansen and Jan Arne Telle},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11479},
  URN =		{urn:nbn:de:0030-drops-114796},
  doi =		{10.4230/LIPIcs.IPEC.2019.18},
  annote =	{Keywords: graph clustering, edge connectivity, parameterized complexity}
}

Keywords: graph clustering, edge connectivity, parameterized complexity
Collection: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI