License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.23
URN: urn:nbn:de:0030-drops-85576
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8557/
Go to the corresponding LIPIcs Volume Portal

Jansen, Bart M. P. ; Pilipczuk, Marcin ; Wrochna, Marcin

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor

pdf-format:
LIPIcs-IPEC-2017-23.pdf (0.5 MB)

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 bounded-size 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 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 bounded-degree and K_{3,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.

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:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8557},
  URN =		{urn:nbn:de:0030-drops-85576},
  doi =		{10.4230/LIPIcs.IPEC.2017.23},
  annote =	{Keywords: Turing kernel, long path, k-path, excluded topological minor, modulator}
}

Keywords: Turing kernel, long path, k-path, excluded topological minor, modulator
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI