### Inhalt des Dokuments

# On the Parameterized Complexity of Graph Bisections

**Dipl.-Inf. René van Bevern
****(TU Berlin)**

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.
The problem has been thoroughly studied in the past. However, only few
results have been published that consider the parameterized complexity
of the 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 Vertex Bisection 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. Thus problem restrictions, such as our
condition on the cut-out components, are unavoidable.

For
Bisection we further show that no polynomial-size kernels exist for
the cut size parameter. This is done by a more general reduction for
the parameter bandwidth, which excludes small kernels for the cut
size, pathwidth, and cliquewidth.

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.

Date | Speaker | Location | Language |
---|---|---|---|

27.06.2013 16:15 | René van
Bevern | TEL
512 | english/german |

Back to the research colloquium site. [1]

_13/