Kernel bounds for disjoint cycles and disjoint paths

DOI10.1016/j.tcs.2011.04.039zbMath1221.68099MaRDI QIDQ638521

Anders Yeo, Hans L. Bodlaender, Steéphan Thomassé

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.039

zbMATH Keywords

algorithms; data reduction; fixed parameter complexity; lower bounds; kernelization; disjoint cycles

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for kernelizations and other preprocessing procedures
• Infeasibility of instance compression and succinct PCPs for NP
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Approximation algorithms for treewidth
• A cubic kernel for feedback vertex set and loop cutset
• On problems without polynomial kernels
• The Moore bound for irregular graphs
• On treewidth approximations.
• Graph minors. XIII: The disjoint paths problem
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• A 4 k ² kernel for feedback vertex set
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A Linear Kernel for Planar Feedback Vertex Set
• A Cubic Kernel for Feedback Vertex Set
• Incompressibility through Colors and IDs
• Kernelization: New Upper and Lower Bound Techniques
• Two Edge Modification Problems without Polynomial Kernels
• On the Computational Complexity of Combinatorial Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Parameterized and Exact Computation