Kernel bounds for path and cycle problems

DOI10.1007/978-3-642-28050-4_12MaRDI QIDQ2891344zbMATH OpenOpenAlexWikidataFDO

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

Publication date 15 June 2012

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.4141

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Abstract: Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

Recommendations

• Kernel bounds for path and cycle problems
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• On Problems without Polynomial Kernels (Extended Abstract)
• On problems without polynomial kernels

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Color-coding
• Cross-composition: a new technique for kernelization lower bounds
• Divide-and-Color
• Graph minors. XIII: The disjoint paths problem
• Improved algorithms for path, matching, and packing problems
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Lower bounds for kernelizations and other preprocessing procedures
• Narrow sieves for parameterized paths and packings
• On problems without polynomial kernels
• On the parameterized complexity of multiple-interval graph problems
• Parametrized complexity theory.
• Research in Computational Molecular Biology
• Spanning Trees with Many Leaves
• The complexity ecology of parameters: An illustration using bounded max leaf number

Cited in

(14)

• Kernel bounds for path and cycle problems
• Complexity of the path avoiding forbidden pairs problem revisited
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernelization using structural parameters on sparse graph classes
• Kernel bounds for disjoint cycles and disjoint paths
• On the parameterized complexity of edge-linked paths
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• New limits to classical and quantum instance compression
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Turing kernelization for finding long paths in graphs excluding a topological minor
• Solving problems on graphs of high rank-width
• Kernel bounds for structural parameterizations of pathwidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891344)