### Page Content

## On Sparsification for Computing Treewidth

**Dr. Bart Jansen (University of Bergen)**

Many optimization problems can be solved efficiently on graphs of bounded treewidth, if a tree decomposition is known. Unfortunately, computing a minimum-width tree decomposition of a graph is NP-hard and can therefore form a bottleneck in such approaches. In the past, it has been observed that the use of heuristic reduction rules speeds up the process of finding tree decompositions significantly. We analyze two aspects of preprocessing for computing treewidth decompositions theoretically, using the framework of parameterized complexity.

Our first result concerns the possibility of polynomial-time sparsification. We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. In particular, the lower bound shows that Treewidth parameterized by the size of a vertex cover does not have a kernel with O(k^{2-e}) bits (unless ...).

Our second result tightens the gap between the upper- and lower bounds for Treewidth parameterized vertex cover. We improve the O(k

Our first result concerns the possibility of polynomial-time sparsification. We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. In particular, the lower bound shows that Treewidth parameterized by the size of a vertex cover does not have a kernel with O(k^{2-e}) bits (unless ...).

Our second result tightens the gap between the upper- and lower bounds for Treewidth parameterized vertex cover. We improve the O(k

^{^3})-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^{^2}) vertices, which can be encoded in O(k^{^3}) bits. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al. (STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.Date | Speaker | Location | Language |
---|---|---|---|

27.11.2013 11:15 | Bart Jansen | TEL 512 | english |