2011/06/21 by Hans L. Bodlaender, Bodlaender, Hans L., Bart M. P. Jansen +3 · 10 citations
Computer Science · Mathematics · #68Q25 #Advanced Graph Theory Research #Combinatorics #Computational Complexity (cs.CC) #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Disjoint sets #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Hamiltonian path #Hamiltonian path problem #Kernelization #Longest path problem #Mathematics #Parameterized complexity #Path (computing) #Shortest path problem #Vertex (graph theory) #Vertex cover #acm:68Q25 #cs.CC #cs.DS #msc:68Q25
paper · pdf · doi:10.48550/arxiv.1106.4141
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2011/06/21 · arxiv created 2011/12/13 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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.