Abstract
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard 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 k-Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size kO(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 bounded-degree and K3,t-minor-free graphs. Moreover, we show that k-Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free 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 H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.
Original language | English |
---|---|
Title of host publication | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |
Editors | D. Lokshtanov, N. Nishimura |
Place of Publication | Dagstuhl |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 13 |
ISBN (Electronic) | 978-3-95977-051-4 |
DOIs | |
Publication status | Published - 1 Feb 2018 |
Event | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 - Vienna, Austria Duration: 6 Sept 2017 → 8 Sept 2017 Conference number: 12 https://algo2017.ac.tuwien.ac.at/ipec |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 89 |
Conference
Conference | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |
---|---|
Abbreviated title | IPEC 2017 |
Country/Territory | Austria |
City | Vienna |
Period | 6/09/17 → 8/09/17 |
Internet address |
Keywords
- Excluded topological minor
- K-path
- Long path
- Modulator
- Turing kernel