TY - GEN

T1 - Clustering to given connectivities

AU - Golovach, Petr A.

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Petr A. Golovach and Dimitrios M. Thilikos; licensed under Creative Commons License CC-BY.

PY - 2019/12

Y1 - 2019/12

N2 - 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 Λ = 〈λ1,..., λ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 Λ. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k) ∙ nO(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 Λ.

AB - 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 Λ = 〈λ1,..., λ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 Λ. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k) ∙ nO(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 Λ.

KW - Edge connectivity

KW - Graph clustering

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85077446595&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85077446595&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2019.18

DO - 10.4230/LIPIcs.IPEC.2019.18

M3 - Conference contribution

AN - SCOPUS:85077446595

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 14th International Symposium on Parameterized and Exact Computation, IPEC 2019

A2 - Jansen, Bart M. P.

A2 - Telle, Jan Arne

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 14th International Symposium on Parameterized and Exact Computation, IPEC 2019

Y2 - 11 September 2019 through 13 September 2019

ER -