Document Open Access Logo

Faster Detours in Undirected Graphs

Authors Shyan Akmal , Virginia Vassilevska Williams , Ryan Williams, Zixuan Xu

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.7.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Shyan Akmal
  • MIT EECS and CSAIL, Cambridge, MA, USA
Virginia Vassilevska Williams
  • MIT EECS and CSAIL, Cambridge, MA, USA
Ryan Williams
  • MIT EECS and CSAIL, Cambridge, MA, USA
Zixuan Xu
  • MIT Mathematics, Cambridge, MA, USA

Funding

  • Akmal, Shyan: Supported in part by NSF grant CCF-2127597.
  • Vassilevska Williams, Virginia: Supported by NSF CCF-2129139.
  • Williams, Ryan: Supported by NSF CCF-1909429.

Acknowledgements

The first author thanks Nicole Wein for several helpful discussions, and Fedor V. Fomin for answering a question about previous algorithms for k-Longest Path.

Cite As Get BibTex

Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu. Faster Detours in Undirected Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.7

Abstract

The k-Detour problem is a basic path-finding problem: given a graph G on n vertices, with specified nodes s and t, and a positive integer k, the goal is to determine if G has an st-path of length exactly dist(s,t) + k, where dist(s,t) is the length of a shortest path from s to t. The k-Detour problem is NP-hard when k is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in f(k)poly(n) time, for f(⋅) as slow-growing as possible.
We present faster algorithms for k-Detour in undirected graphs, running in 1.853^k poly(n) randomized and 4.082^kpoly(n) deterministic time. The previous fastest algorithms for this problem took 2.746^k poly(n) randomized and 6.523^k poly(n) deterministic time [Bezáková-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length k in undirected graphs [Björklund-Husfeldt-Kaski-Koivisto, JCSS 2017], intuitively by looking for paths of length k in randomly bipartitioned subgraphs. Our algorithms for k-Detour stem from a new application of this idea, which does not involve choosing the bipartitioned subgraphs randomly.
Our work has direct implications for the k-Longest Detour problem, another related path-finding problem. In this problem, we are given the same input as in k-Detour, but are now tasked with determining if G has an st-path of length at least dist(s,t)+k. Our results for k-Detour imply that we can solve k-Longest Detour in 3.432^k poly(n) randomized and 16.661^k poly(n) deterministic time. The previous fastest algorithms for this problem took 7.539^k poly(n) randomized and 42.549^k poly(n) deterministic time [Fomin et al., STACS 2022].

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • path finding
  • detours
  • parameterized complexity
  • exact algorithms

Metrics

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

Related Versions

References

  1. Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu. Faster detours in undirected graphs, 2023. URL: https://arxiv.org/abs/2307.01781.
  2. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.54.
  3. 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, August 2017. URL: https://doi.org/10.1016/j.jcss.2017.03.003.
  4. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1-91:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.91.
  5. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  6. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. Journal of the ACM, 65(3):1-46, March 2018. URL: https://doi.org/10.1145/3148227.
  7. Eduard Eiben, Tomohiro Koana, and Magnus Wahlström. Determinantal sieving, 2023. URL: https://doi.org/10.48550/arXiv.2304.02091.
  8. Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.29.
  9. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Long directed (s, t)-path: FPT algorithm. Information Processing Letters, 140:8-12, December 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.018.
  10. Ashwin Jacob, Michał Włodarczyk, and Meirav Zehavi. Long directed detours: Reduction to 2-disjoint paths, 2023. URL: https://doi.org/10.48550/arXiv.2301.06105.
  11. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Automata, Languages and Programming, 35th International Colloquium, ICALP, volume 5125 of Lecture Notes in Computer Science, pages 575-586. Springer, 2008. Google Scholar
  12. Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. ACM Transactions on Algorithms, 12(3):1-18, May 2016. URL: https://doi.org/10.1145/2885499.
  13. Burkhard Monien. How to find long paths efficiently. In North-Holland Mathematics Studies, volume 109, pages 239-254. Elsevier, 1985. Google Scholar
  14. Jesper Nederlof. Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ACM, June 2020. URL: https://doi.org/10.1145/3357713.3384264.
  15. Dekel Tsur. Faster deterministic parameterized algorithm for k-path. Theoretical Computer Science, 790:96-104, October 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.024.
  16. Ryan Williams. Finding paths of length k in O^∗(2^k) time. Inf. Process. Lett., 109(6):315-318, February 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
  17. Meirav Zehavi. A randomized algorithm for long directed cycle. Information Processing Letters, 116(6):419-422, June 2016. URL: https://doi.org/10.1016/j.ipl.2016.02.005.
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