Jansen, Bart M. P. ;
Pilipczuk, Marcin ;
Wrochna, Marcin
Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
Abstract
The notion of Turing kernelization investigates whether a polynomialtime algorithm can solve an NPhard problem, when it is aided by an oracle that can be queried for the answers to boundedsize subproblems. One of the main open problems in this direction is whether kPATH admits a polynomial Turing kernel: can a polynomialtime algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}?
We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for boundeddegree and K_{3,t}minorfree graphs. Moreover, we show that kPATH even admits a polynomial Turing kernel when the input graph is not Htopologicalminorfree itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any Htopologicalminorfree graph that does not contain a kpath has a separation that can safely be reduced after communication with the oracle.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2018:8557,
author = {Bart M. P. Jansen and Marcin Pilipczuk and Marcin Wrochna},
title = {{Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {23:123:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8557},
URN = {urn:nbn:de:0030drops85576},
doi = {10.4230/LIPIcs.IPEC.2017.23},
annote = {Keywords: Turing kernel, long path, kpath, excluded topological minor, modulator}
}
02.03.2018
Keywords: 

Turing kernel, long path, kpath, excluded topological minor, modulator 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 