Polynomial kernels for hitting forbidden minors under structural parameterizations
From MaRDI portal
Abstract: We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G,k) can be reduced in polynomial time to an equivalent one of size . In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-Deletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth . We prove that for each set F of connected graphs and constant , the F-Deletion problem parameterized by the size of a treedepth- modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-Deletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G-X. By bounding the number of different types of behavior that can occur by a polynomial in |X|, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-Deletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for F-Deletion parameterized by a vertex cover, which is a treedepth-one modulator.
Recommendations
Cites work
- (Meta) kernelization
- A 4k^2 kernel for feedback vertex set
- A faster parameterized algorithm for treedepth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Easy problems for tree-decomposable graphs
- Fundamentals of parameterized complexity
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Hitting forbidden minors: approximation and kernelization
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- scientific article; zbMATH DE number 1323192 (Why is no real title available?)
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization using structural parameters on sparse graph classes
- Kernelization. Theory of parameterized preprocessing
- Kernelization: new upper and lower bound techniques
- New limits to classical and quantum instance compression
- On problems without polynomial kernels
- On space efficiency of algorithms working on structural decompositions of graphs
- On the hardness of losing width
- One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
- Parameterized algorithms
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Recent developments in kernelization: a survey
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Sparsity. Graphs, structures, and algorithms
- Structural Parameterizations of Feedback Vertex Set
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Where first-order and monadic second-order logic coincide
Cited in
(12)- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- 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
- Hitting forbidden minors: approximation and kernelization
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Kernelization for feedback vertex set via elimination distance to a forest
- On the lossy kernelization for connected treedepth deletion set
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Approximate Turing kernelization for problems parameterized by treewidth
- Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs
This page was built for publication: Polynomial kernels for hitting forbidden minors under structural parameterizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2202024)
