Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
From MaRDI portal
Abstract: The notion of treewidth plays an important role in theoretical and practical studies of graph problems. It has been recognized that, especially in practical environments, when computing the treewidth of a graph it is invaluable to first apply an array of preprocessing rules that simplify and shrink it. This work seeks to prove rigorous performance guarantees for such preprocessing rules, both known and new ones, by studying them in the framework of kernelization from parameterized complexity. It is known that the NP-complete problem of determining whether a given graph G has treewidth at most k admits no polynomial-time preprocessing algorithm that reduces any input instance to size polynomial in k, unless NP is in coNP/poly and the polynomial hierarchy collapses to its third level. In this paper we therefore consider structural graph measures larger than treewidth, and determine whether efficient preprocessing can shrink the instance size to a polynomial in such a parameter value. We prove that given an instance (G,k) of treewidth we can efficiently reduce its size to O(fvs(G)^4) vertices, where fvs(G) is the size of a minimum feedback vertex set in G. We can also prove a size reduction to O(vc(G)^3) vertices, where vc(G) is the size of a minimum vertex cover. Phrased in the language of parameterized complexity, we show that Treewidth has a polynomial kernel when parameterized by the size of a given feedback vertex set, and also by the size of a vertex cover. In contrast we show that Treewidth parameterized by the vertex-deletion distance to a single clique, and Weighted Treewidth parameterized by the size of a vertex cover, do not admit polynomial kernelizations unless NP is in coNP/poly.
Recommendations
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Treewidth: Characterizations, Applications, and Computations
- scientific article; zbMATH DE number 1361465
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- On treewidth approximations
- Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday
- Treewidth and the Computational Complexity of MAP Approximations
- Treewidth computations. I: Upper bounds
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity of Finding Embeddings in a k-Tree
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Contraction and Treewidth Lower Bounds
- Cross-composition: a new technique for kernelization lower bounds
- Heuristic and metaheuristic methods for computing graph treewidth
- scientific article; zbMATH DE number 176761 (Why is no real title available?)
- scientific article; zbMATH DE number 1982177 (Why is no real title available?)
- Necessary edges in k-chordalisations of graphs
- On problems without polynomial kernels
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Safe reduction rules for weighted treewidth
- Safe separators for treewidth
- The Pathwidth and Treewidth of Cographs
Cited in
(18)- On the hardness of losing width
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On the hardness of losing width
- On cutwidth parameterized by vertex cover
- Kernelization -- preprocessing with a guarantee
- Fixed-parameter tractability of treewidth and pathwidth
- Dual parameterization and parameterized approximability of subset graph problems
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Treewidth computation and kernelization in the parallel external memory model
- New limits to classical and quantum instance compression
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- On cutwidth parameterized by vertex cover
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Kernelization of packing problems
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Safe reduction rules for weighted treewidth
This page was built for publication: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012824)
