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 language | English |
---|---|
Title of host publication | Algorithms - ESA 2014 (22nd European Symposium on Algorithms, Wroclaw, Poland, September 8-10, 2014. Proceedings) |
Editors | A.S. Schulz, D. Wagner |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 579-591 |
ISBN (Print) | 978-3-662-44776-5 |
DOIs | |
Publication status | Published - 2014 |
Externally published | Yes |
Event | 22nd Annual European Symposium on Algorithms (ESA 2014) - Wrocław, Poland Duration: 8 Sept 2014 → 10 Sept 2014 Conference number: 22 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 8737 |
ISSN (Print) | 0302-9743 |
Conference
Conference | 22nd Annual European Symposium on Algorithms (ESA 2014) |
---|---|
Abbreviated title | ESA 2014 |
Country/Territory | Poland |
City | Wrocław |
Period | 8/09/14 → 10/09/14 |