## René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondřej Suchý.
On the parameterized complexity of computing balanced partitions in
graphs.
*Theory of Computing Systems*, 57(1):1–35, 2015.

A balanced partition is a clustering of a graph into a
given number of equal-sized parts. For instance, the
Bisection problem asks to remove at most k edges in
order to partition the vertices into two equal-sized
parts. We prove that Bisection is FPT for the distance
to constant cliquewidth if we are given the deletion
set. This implies FPT algorithms for some well-studied
parameters such as cluster vertex deletion number and
feedback vertex set. However, we show that Bisection
does not admit polynomial-size kernels for these
parameters. For the Vertex Bisection problem, vertices
need to be removed in order to obtain two equal-sized
parts. We show that this problem is FPT for the number
of removed vertices k if the solution cuts the graph
into a constant number c of connected components. The
latter condition is unavoidable, since we also prove
that Vertex Bisection is W[1]-hard w.r.t. (k,c). Our
algorithms for finding bisections can easily be
adapted to finding partitions into d equal-sized
parts, which entails additional running time factors
of n^O(d). We show that a substantial speed-up is
unlikely since the corresponding task is W[1]-hard
w.r.t. d, even on forests of maximum degree two. We
can, however, show that it is FPT for the vertex cover
number.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*