A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
DOI10.1016/j.jcss.2021.02.005zbMath1482.68110OpenAlexW4253478214MaRDI QIDQ2662677
Bart M. P. Jansen, Huib Donkers
Publication date: 14 April 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2021.02.005
parameterized complexityTuring kernelizationkernelizationhardness of kernelizationparamterized algorithms
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Two-layer planarization parameterized by feedback edge set
- Data reduction for graph coloring problems
- Infeasibility of instance compression and succinct PCPs for NP
- Graph minors. XX: Wagner's conjecture
- Turing kernelization for finding long paths and cycles in restricted graph classes
- A cubic kernel for feedback vertex set and loop cutset
- The node-deletion problem for hereditary properties is NP-complete
- A partial k-arboretum of graphs with bounded treewidth
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph minors. XIII: The disjoint paths problem
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- A completeness theory for polynomial (Turing) kernelization
- On the hardness of losing width
- Hitting Forbidden Minors: Approximation and Kernelization
- Kernelization – Preprocessing with a Guarantee
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Kernel(s) for problems with no kernel
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- Kernelization: New Upper and Lower Bound Techniques
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Kernelization
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Compression via Matroids
- Parameterized and Exact Computation
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
This page was built for publication: A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
