Preprocessing subgraph and minor problems: when does a small vertex cover help?
From MaRDI portal
Abstract: We prove a number of results around kernelization of problems parameterized by the size of a given vertex cover of the input graph. We provide three sets of simple general conditions characterizing problems admitting kernels of polynomial size. Our characterizations not only give generic explanations for the existence of many known polynomial kernels for problems like q-Coloring, Odd Cycle Transversal, Chordal Deletion, Eta Transversal, or Long Path, parameterized by the size of a vertex cover, but also imply new polynomial kernels for problems like F-Minor-Free Deletion, which is to delete at most k vertices to obtain a graph with no minor from a fixed finite set F. While our characterization captures many interesting problems, the kernelization complexity landscape of parameterizations by vertex cover is much more involved. We demonstrate this by several results about induced subgraph and minor containment testing, which we find surprising. While it was known that testing for an induced complete subgraph has no polynomial kernel unless NP is in coNP/poly, we show that the problem of testing if a graph contains a complete graph on t vertices as a minor admits a polynomial kernel. On the other hand, it was known that testing for a path on t vertices as a minor admits a polynomial kernel, but we show that testing for containment of an induced path on t vertices is unlikely to admit a polynomial kernel.
Recommendations
- Preprocessing subgraph and minor problems: When does a small vertex cover help?
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
- Hitting forbidden minors: approximation and kernelization
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- (Meta) Kernelization
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems for restrictions of treewidth
- Bidimensionality and kernels
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Cross-composition: a new technique for kernelization lower bounds
- Data reduction for graph coloring problems
- Graph Classes: A Survey
- Graph minors. XX: Wagner's conjecture
- Graph theory
- Incompressibility through Colors and IDs
- Induced matchings
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernel bounds for path and cycle problems
- Kernel bounds for structural parameterizations of pathwidth
- Kernel(s) for problems with no kernel
- Kernelization: new upper and lower bound techniques
- Logic, graphs, and algorithms
- On cutwidth parameterized by vertex cover
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On problems without polynomial kernels
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On the hardness of losing width
- Parametrized complexity theory.
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Reflections on multivariate algorithmics and problem parameterization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Solving MAX-\(r\)-SAT above a tight lower bound
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The strong perfect graph theorem
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
Cited in
(19)- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Preprocessing subgraph and minor problems: When does a small vertex cover help?
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Approximation and kernelization for chordal vertex deletion
- Fixed parameter tractability of graph deletion problems over data streams
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Kernelization using structural parameters on sparse graph classes
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Streaming deletion problems parameterized by vertex cover
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Meta-kernelization using well-structured modulators
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Polynomial Kernel for Interval Vertex Deletion
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
- Streaming deletion problems Parameterized by vertex cover
This page was built for publication: Preprocessing subgraph and minor problems: when does a small vertex cover help?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386050)
