Sie sind hier

# 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