Kernel bounds for path and cycle problems

DOI10.1016/j.tcs.2012.09.006zbMath1407.68207OpenAlexW1796863810WikidataQ59567509 ScholiaQ59567509MaRDI QIDQ392032

Stefan Kratsch, Bart M. P. Jansen, Hans L. Bodlaender

Publication date: 13 January 2014

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

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

zbMATH Keywords

upper boundsgraphslower boundsparameterized complexitykernelizationpath and cycle problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Meta-kernelization using well-structured modulators ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ On the complexity of approximately matching a string to a directed graph ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ A completeness theory for polynomial (Turing) kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Kernel bounds for disjoint cycles and disjoint paths
• Monadic second-order evaluations on tree-decomposable graphs
• The complexity ecology of parameters: An illustration using bounded max leaf number
• On the complexity of paths avoiding forbidden pairs
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• On the complexity of approximating the independent set problem
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Graph minors. XIII: The disjoint paths problem
• Narrow sieves for parameterized paths and packings
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Tight Bounds for Linkages in Planar Graphs
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• A Dynamic Programming Approach to Sequencing Problems
• Spanning Trees with Many Leaves
• Easy problems for tree-decomposable graphs
• Divide-and-Color
• Incompressibility through Colors and IDs
• Color-coding
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Kernel bounds for path and cycle problems