Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

In experimental evaluations and applications the bottleneck often is to find a tree decomposition of small width. There are many heuristics as well as a few (time-costly) exact algorithms. It is natural to start such a computation with a (heuristic) preprocessing based on a set of safe reduction rules, e.g., handling simplicial vertices. Experimental results have reported significant size reductions for many practical instances, however only few theoretical results are known.

In joint work with Hans Bodlaender and Bart Jansen, we show small problem kernels (i.e. efficient preprocessing with a good performance guarantee) for treewidth of graphs having a small vertex cover or feedback vertex set. Complementing these positive results, we show that under a standard complexity assumption there are no polynomial kernels when parameterizing by the distance to two other simple graph classes, as well as for weighted treewidth parameterized by a vertex cover.