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

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

8 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages579-591
ISBN (Print)978-3-662-44776-5
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event22nd Annual European Symposium on Algorithms (ESA 2014) - Wrocław, Poland
Duration: 8 Sep 201410 Sep 2014
Conference number: 22

Publication series

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

Conference

Conference22nd Annual European Symposium on Algorithms (ESA 2014)
Abbreviated titleESA 2014
CountryPoland
CityWrocław
Period8/09/1410/09/14

Fingerprint 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