On the parameterized complexity of computing graph bisections. / Van Bevern, René; Feldmann, Andreas Emil; Sorge, Manuel et al.
Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Revised Papers. Springer-Verlag GmbH and Co. KG, 2013. p. 76-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8165 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On the parameterized complexity of computing graph bisections
AU - Van Bevern, René
AU - Feldmann, Andreas Emil
AU - Sorge, Manuel
AU - Suchý, Ondřej
PY - 2013/1/1
Y1 - 2013/1/1
N2 - The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, only few results have been published that consider the parameterized complexity of this problem. We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components. For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tractability for the distance to constant cliquewidth if we are given the deletion set. This implies fixed-parameter algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set.
AB - The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, only few results have been published that consider the parameterized complexity of this problem. We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components. For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tractability for the distance to constant cliquewidth if we are given the deletion set. This implies fixed-parameter algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set.
UR - http://www.scopus.com/inward/record.url?scp=84893120914&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45043-3_8
DO - 10.1007/978-3-642-45043-3_8
M3 - Conference contribution
AN - SCOPUS:84893120914
SN - 9783642450426
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 76
EP - 87
BT - Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Revised Papers
PB - Springer-Verlag GmbH and Co. KG
T2 - 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013
Y2 - 19 June 2013 through 21 June 2013
ER -
ID: 22340792