Polynomial kernels for hitting forbidden minors under structural parameterizations
From MaRDI portal
Publication:2202024
DOI10.1016/j.tcs.2020.07.009zbMath1455.68143arXiv1804.08885OpenAlexW2964248725MaRDI QIDQ2202024
Astrid Pieterse, Bart M. P. Jansen
Publication date: 17 September 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1804.08885
Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, 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, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Cites Work
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Sparsity. Graphs, structures, and algorithms
- Infeasibility of instance compression and succinct PCPs for NP
- On problems without polynomial kernels
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Polynomial kernels for vertex cover parameterized by small degree modulators
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- On the hardness of losing width
- Vertex Cover: Further Observations and Further Improvements
- Hitting Forbidden Minors: Approximation and Kernelization
- A 4 k 2 kernel for feedback vertex set
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- (Meta) Kernelization
- Vertex Cover Structural Parameterization Revisited
- Easy problems for tree-decomposable graphs
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- New Limits to Classical and Quantum Instance Compression
- Kernelization: New Upper and Lower Bound Techniques
- Vertex packings: Structural properties and algorithms
- One Hierarchy Spawns Another
- Structural Parameterizations of Feedback Vertex Set
- Kernelization
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
- A Faster Parameterized Algorithm for Treedepth
- Where First-Order and Monadic Second-Order Logic Coincide
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
