Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.23.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Bart M. P. Jansen
Marcin Pilipczuk
Marcin Wrochna

Cite As Get BibTex

Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.23

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.

Subject Classification

Keywords
  • Turing kernel
  • long path
  • k-path
  • excluded topological minor
  • modulator

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M. S. Ramanujan. On the kernelization complexity of colorful motifs. In Venkatesh Raman and Saket Saurabh, editors, Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of Lecture Notes in Computer Science, pages 14-25. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17493-3_4.
  2. Florian Barbero, Christophe Paul, and Michał Pilipczuk. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs. In Proc. 44th ICALP, 2017. In press. Google Scholar
  3. Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. ACM Trans. Algorithms, 8(4):38:1-38:19, 2012. URL: http://dx.doi.org/10.1145/2344422.2344428.
  4. Hans L. Bodlaender, Erik D. Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, Moritz Müller, Venkatesh Raman, Johan van Rooij, and Frances A. Rosamond. Open problems in parameterized and exact computation - IWPEC 2008. Technical Report UU-CS-2008-017, Utrecht University, 2008. Google Scholar
  5. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  6. Guantao Chen, Zhicheng Gao, Xingxing Yu, and Wenan Zang. Approximating longest cycles in graphs with bounded degrees. SIAM J. Comput., 36(3):635-656, 2006. Google Scholar
  7. Guantao Chen, Xingxing Yu, and Wenan Zang. The circumference of a graph with no K_3, t-minor, II. J. Comb. Theory, Ser. B, 102(6):1211-1240, 2012. Google Scholar
  8. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 323-332. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591852.
  9. G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, s3-2(1):69-81, 1952. URL: http://dx.doi.org/10.1112/plms/s3-2.1.69.
  10. Jan-Oliver Fröhlich and Theodor Müller. Linear connectivity forces large complete bipartite minors: An alternative approach. J. Comb. Theory, Ser. B, 101(6):502-508, 2011. URL: http://dx.doi.org/10.1016/j.jctb.2011.02.002.
  11. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.09.002.
  12. Valentin Garnero and Mathias Weller. Parameterized certificate dispersal and its variants. Theor. Comput. Sci., 622:66-78, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.02.001.
  13. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput., 44(1):114-159, 2015. URL: http://dx.doi.org/10.1137/120892234.
  14. Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (turing) kernelization. Algorithmica, 71(3):702-730, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9910-8.
  15. Falk Hüffner, Christian Komusiewicz, and Manuel Sorge. Finding highly connected subgraphs. In Proc. 41st SOFSEM, pages 254-265, 2015. Google Scholar
  16. Bart M. P. Jansen. Turing kernelization for finding long paths and cycles in restricted graph classes. J. Comput. Syst. Sci., 85:18-37, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.10.008.
  17. Bart M. P. Jansen and Dániel Marx. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and turing kernels. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 616-629. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.42.
  18. Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. Turing kernelization for finding long paths in graph classes excluding a topological minor. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1707.01797.
  19. Sudeshna Kolay and Fahad Panolan. Parameterized algorithms for deletion to (r, ell)-graphs. In Prahladh Harsha and G. Ramalingam, editors, 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, volume 45 of LIPIcs, pages 420-433. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.420.
  20. Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Manuscript, 2017. Google Scholar
  21. Neil Robertson and Paul D. Seymour. Graph minors: XVII. taming a vortex. J. Comb. Theory, Ser. B, 77(1):162-210, 1999. URL: http://dx.doi.org/10.1006/jctb.1999.1919.
  22. Alexander Schäfer, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Parameterized computational complexity of finding small-diameter subgraphs. Optimization Letters, 6(5):883-891, 2012. URL: http://dx.doi.org/10.1007/s11590-011-0311-5.
  23. Songling Shan. Homeomorphically Irreducible Spanning Trees, Halin Graphs, and Long Cycles in 3-connected Graphs with Bounded Maximum Degrees. PhD thesis, Georgia State University, 2015. URL: http://scholarworks.gsu.edu/math_diss/23/.
  24. Stéphan Thomassé, Nicolas Trotignon, and Kristina Vuskovic. A polynomial Turing-kernel for weighted independent set in bull-free graphs. In Proc. 40th WG, pages 408-419. Springer, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact