Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs
From MaRDI portal
Publication:2828227
DOI10.1145/2691321zbMath1347.68171OpenAlexW2090698092MaRDI QIDQ2828227
Venkatesh Raman, Ashutosh Rai, Marcin Pilipczuk, Stefan Kratsch
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2691321
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Essentially tight kernels for (weakly) closed graphs ⋮ On the parameterized complexity of reconfiguration problems ⋮ Tractability of König edge deletion problems ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Chordal deletion is fixed-parameter tractable
- On problems without polynomial kernels
- The node-deletion problem for hereditary properties is NP-complete
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Parameterized complexity of finding subgraphs with hereditary properties.
- Algorithmic graph theory and perfect graphs
- Proper interval vertex deletion
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- Measuring Indifference: Unit Interval Vertex Deletion
- Incompressibility through Colors and IDs
- Kernelization Lower Bounds by Cross-Composition
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Ramsey-type theorems with forbidden subgraphs
This page was built for publication: Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs
