Turing kernelization for finding long paths and cycles in restricted graph classes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)


We analyze the potential for provably effective preprocessing for the problems of finding paths and cycles with at least k edges. Several years ago, the question was raised whether the existing superpolynomial kernelization lower bounds for k-Path and k-Cycle can be circumvented by relaxing the requirement that the preprocessing algorithm outputs a single instance. To this date, very few examples are known where the relaxation to Turing kernelization is fruitful. We provide a novel example by giving polynomial-size Turing kernels for k-Path and k-Cycle on planar graphs, graphs of maximum degree t, claw-free graphs, and K 3,t -minor-free graphs, for each constant t¿=¿3. The result for planar graphs solves an open problem posed by Lokshtanov. Our kernelization schemes are based on a new methodology called Decompose-Query-Reduce.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2014 (22nd European Symposium on Algorithms, Wroclaw, Poland, September 8-10, 2014. Proceedings)
EditorsA.S. Schulz, D. Wagner
Place of PublicationBerlin
ISBN (Print)978-3-662-44776-5
Publication statusPublished - 2014
Externally publishedYes
Event22nd Annual European Symposium on Algorithms (ESA 2014) - Wrocław, Poland
Duration: 8 Sept 201410 Sept 2014
Conference number: 22

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference22nd Annual European Symposium on Algorithms (ESA 2014)
Abbreviated titleESA 2014


Dive into the research topics of 'Turing kernelization for finding long paths and cycles in restricted graph classes'. Together they form a unique fingerprint.

Cite this