Kernel bounds for path and cycle problems

Hans L. Bodlaender; B.M.P. Jansen; Stefan Kratsch

doi:10.1007/978-3-642-28050-4_12

Kernel bounds for path and cycle problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 Citations (Scopus)

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.

Original language	English
Title of host publication	Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers
Pages	145-158
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-28050-4_12
Publication status	Published - 2012
Externally published	Yes
Event	6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrucken, Germany Duration: 6 Sept 2011 → 8 Sept 2011 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Volume	7112
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Abbreviated title	IPEC 2011
Country/Territory	Germany
City	Saarbrucken
Period	6/09/11 → 8/09/11

Access to Document

10.1007/978-3-642-28050-4_12

Cite this

@inproceedings{a907024420f749b28101aa350bdbd35f,

title = "Kernel bounds for path and cycle problems",

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.",

author = "Bodlaender, {Hans L.} and B.M.P. Jansen and Stefan Kratsch",

year = "2012",

doi = "10.1007/978-3-642-28050-4_12",

language = "English",

isbn = "9783642280498",

series = "Lecture Notes in Computer Science",

pages = "145--158",

booktitle = "Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers",

note = "6th International Symposium on Parameterized and Exact Computation, IPEC 2011, IPEC 2011 ; Conference date: 06-09-2011 Through 08-09-2011",

}

Bodlaender, HL, Jansen, BMP & Kratsch, S 2012, Kernel bounds for path and cycle problems. in Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7112, pp. 145-158, 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, Saarbrucken, Germany, 6/09/11. https://doi.org/10.1007/978-3-642-28050-4_12

Kernel bounds for path and cycle problems. / Bodlaender, Hans L.; Jansen, B.M.P.; Kratsch, Stefan.
Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. 2012. p. 145-158 (Lecture Notes in Computer Science; Vol. 7112).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Kernel bounds for path and cycle problems

AU - Bodlaender, Hans L.

AU - Jansen, B.M.P.

AU - Kratsch, Stefan

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84858380790&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28050-4_12

DO - 10.1007/978-3-642-28050-4_12

M3 - Conference contribution

AN - SCOPUS:84858380790

SN - 9783642280498

T3 - Lecture Notes in Computer Science

SP - 145

EP - 158

BT - Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers

T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011

Y2 - 6 September 2011 through 8 September 2011

ER -

Kernel bounds for path and cycle problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this