## René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondřej Suchý.
On the parameterized complexity of computing graph bisections.
In *Proceedings of the 39th International Workshop on
Graph-Theoretic Concepts in Computer Science (WG'13), Lübeck, Germany*,
volume 8165 of *Lecture Notes in Computer Science*, pages 76–87.
Springer, 2013.
The final version of this article appeared in Theory of Computing
Systems.

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.

[ bib |
DOI |
slides |
journal version ]
Back

*This file was generated by
bibtex2html 1.98.*