Kernel bounds for path and cycle problems

DOI10.1007/978-3-642-28050-4_12zbMATH Open1352.68092arXiv1106.4141OpenAlexW2568069351WikidataQ59567543 ScholiaQ59567543MaRDI QIDQ2891344FDOQ2891344

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Kernel bounds for path and cycle problems
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernelization using structural parameters on sparse graph classes
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• 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
• Complexity of the path avoiding forbidden pairs problem revisited

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)