Document Open Access Logo

Detours in Directed Graphs

Authors Fedor V. Fomin , Petr A. Golovach , William Lochet , Danil Sagunov , Kirill Simonov, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.29.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
William Lochet
  • Department of Informatics, University of Bergen, Norway
Danil Sagunov
  • St. Petersburg Department of V.A. Steklov Institute of Mathematics, Russia
  • JetBrains Research, Saint Petersburg, Russia
Kirill Simonov
  • Algorithms and Complexity Group, TU Wien, Austria
Saket Saurabh
  • Institute of Mathematical Sciences, HBNI, Chennai, India
  • Department of Informatics, University of Bergen, Norway

Funding

  • Fomin, Fedor V.: supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Golovach, Petr A.: supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Lochet, William: supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416).
  • Sagunov, Danil: supported by Leonhard Euler International Mathematical Institute in Saint Petersburg (agreement no. 075-15-2019-1620).
  • Simonov, Kirill: supported by the Austrian Science Fund (FWF) via project Y1329 (Parameterized Analysis in Artificial Intelligence).
  • Saurabh, Saket: supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416) and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.29

Abstract

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. [Ivona Bezáková et al., 2019] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O(k)}⋅ n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O (k)}· n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k(diam(G)denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1,..., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • longest path
  • longest detour
  • diameter
  • directed graphs
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving MAX-r-SAT above a tight lower bound. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 511-517. SIAM, 2010. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. Springer, 2009. Google Scholar
  4. Jørgen Bang-Jensen, Yannis Manoussakis, and Carsten Thomassen. A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs. J. Algorithms, 13(1):114-127, 1992. URL: https://doi.org/10.1016/0196-6774(92)90008-Z.
  5. Eli Berger, Paul Seymour, and Sophie Spirkl. Finding an induced path that is not a shortest path, 2020. URL: http://arxiv.org/abs/2005.12861.
  6. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding detours is fixed-parameter tractable. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), volume 80 of LIPIcs, pages 54:1-54:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.54.
  7. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding detours is fixed-parameter tractable. SIAM J. Discret. Math., 33(4):2326-2345, 2019. URL: https://doi.org/10.1137/17M1148566.
  8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences, 87:119-139, 2017. URL: https://doi.org/10.1016/j.jcss.2017.03.003.
  9. Hans L. Bodlaender. On linear time minor tests with depth-first search. Journal of Algorithms, 14(1):1-23, 1993. URL: https://doi.org/10.1006/jagm.1993.1001.
  10. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  11. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  12. Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang. Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM Journal on Computing, 38(6):2526-2547, 2009. URL: https://doi.org/10.1137/080716475.
  13. Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Improved algorithms for path, matching, and packing problems. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 298-307. SIAM, 2007. Google Scholar
  14. Maria Chudnovsky, Alex Scott, and Paul D. Seymour. Excluding pairs of graphs. J. Comb. Theory, Ser. B, 106:15-29, 2014. URL: https://doi.org/10.1016/j.jctb.2014.01.001.
  15. Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 24 of LIPIcs, pages 43-54. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2013.43.
  16. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  17. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 197-206. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.29.
  18. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 150-159. IEEE, 2011. Google Scholar
  19. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  20. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  21. Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in directed graphs. CoRR, abs/2201.03318, 2022. URL: http://arxiv.org/abs/2201.03318.
  22. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going far from degeneracy. SIAM J. Discret. Math., 34(3):1587-1601, 2020. URL: https://doi.org/10.1137/19M1290577.
  23. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Parameterization Above a Multiplicative Guarantee. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1-39:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.39.
  24. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Algorithmic extensions of Dirac’s Theorem. CoRR, abs/2011.03619, 2020. URL: http://arxiv.org/abs/2011.03619.
  25. Fedor V. Fomin and Petteri Kaski. Exact exponential algorithms. Communications of the ACM, 56(3):80-88, 2013. URL: https://doi.org/10.1145/2428556.2428575.
  26. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  27. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative families of product families. ACM Trans. Algorithms, 13(3):36:1-36:29, 2017. URL: https://doi.org/10.1145/3039243.
  28. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Long directed (s, t)-path: FPT algorithm. Inf. Process. Lett., 140:8-12, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.018.
  29. Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111-121, 1980. URL: https://doi.org/10.1016/0304-3975(80)90009-2.
  30. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  31. Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1152-1166. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch80.
  32. Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory of Computing Systems, 48(2):402-410, 2011. URL: https://doi.org/10.1007/s00224-010-9262-y.
  33. Gregory Gutin, Leo van Iersel, Matthias Mnich, and Anders Yeo. Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. Journal of Computer and System Sciences, 78(1):151-163, 2012. URL: https://doi.org/10.1016/j.jcss.2011.01.004.
  34. Gregory Z. Gutin and Viresh Patel. Parameterized traveling salesman problem: Beating the average. SIAM J. Discrete Math., 30(1):220-238, 2016. Google Scholar
  35. Gregory Z. Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst., 41(3):521-538, 2007. URL: https://doi.org/10.1007/s00224-007-1330-6.
  36. Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica, 52(2):114-132, 2008. URL: https://doi.org/10.1007/s00453-007-9008-7.
  37. Bart M. P. Jansen, László Kozma, and Jesper Nederlof. Hamiltonicity below Dirac’s condition. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 11789 of Lecture Notes in Computer Science, pages 27-39. Springer, 2019. Google Scholar
  38. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. J. Comb. Theory, Ser. B, 102(2):424-435, 2012. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
  39. Ken-ichi Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 655-664. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746586.
  40. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Divide-and-color. In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 4271 of Lecture Notes in Computer Science, pages 58-67. Springer, 2006. URL: https://doi.org/10.1007/11917496_6.
  41. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5125 of Lecture Notes in Computer Science, pages 575-586. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_47.
  42. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Communications of the ACM, 59(1):98-105, 2016. URL: https://doi.org/10.1145/2742544.
  43. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: https://doi.org/10.1145/2566616.
  44. Meena Mahajan and Venkatesh Raman. Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms, 31(2):335-354, 1999. URL: https://doi.org/10.1006/jagm.1998.0996.
  45. Meena Mahajan, Venkatesh Raman, and Somnath Sikdar. Parameterizing above or below guaranteed values. Journal of Computer and System Sciences, 75(2):137-153, 2009. URL: https://doi.org/10.1016/j.jcss.2008.08.004.
  46. Burkhard Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems, volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. URL: https://doi.org/10.1016/S0304-0208(08)73110-4.
  47. Neil Robertson and Paul D. Seymour. Graph minors. XIII. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  48. Alexander Schrijver. Finding k disjoint paths in a directed planar graph. SIAM J. Comput., 23(4):780-788, 1994. URL: https://doi.org/10.1137/S0097539792224061.
  49. Carsten Thomassen. Hamiltonian-connected tournaments. J. Comb. Theory, Ser. B, 28(2):142-163, 1980. URL: https://doi.org/10.1016/0095-8956(80)90061-1.
  50. Dekel Tsur. Faster deterministic parameterized algorithm for k-path. Theor. Comput. Sci., 790:96-104, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.024.
  51. Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letters, 109(6):315-318, 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
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 Imprint Privacy Contact