Document Open Access Logo

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Authors Ran Duan, Hanlin Ren

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.42.pdf
  • Filesize: 458 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph Theory
  • Approximation Algorithms
  • Combinatorial Optimization

Metrics

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

Abstract

In the bounded-leg shortest path (BLSP) problem, we are given a weighted graph G with nonnegative edge lengths, and we want to answer queries of the form "what's the shortest path from u to v, where only edges of length <=L are considered?". A more general problem is the APSP-AF (all-pair shortest path for all flows) problem, in which each edge has two weights - a length d and a capacity f, and a query asks about the shortest path from u to v where only edges of capacity >= f are considered.
In this article we give an O~(n^{(omega+3)/2}epsilon^{-3/2}log W) time algorithm to compute a data structure that answers APSP-AF queries in O(log(epsilon^{-1}log (nW))) time and achieves (1+epsilon)-approximation, where omega < 2.373 is the exponent of time complexity of matrix multiplication, W is the upper bound of integer edge lengths, and n is the number of vertices. This is the first truly-subcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time max-min product algorithm [Duan and Pettie 2009]. Since the all-pair bottleneck path (APBP) problem, which is equivalent to max-min product, can be seen as all-pair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.

Cite As Get BibTex

Ran Duan and Hanlin Ren. Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.42

Author Details

Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, China
Hanlin Ren
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, China

Funding

  • Duan, Ran: R. Duan is supported by a China Youth 1000-Talent grant.

References

  1. Giorgio Ausiello, Giuseppe F Italiano, Alberto Marchetti Spaccamela, and Umberto Nanni. Incremental algorithms for minimal length paths. Journal of Algorithms, 12(4):615-638, 1991. Google Scholar
  2. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Journal of Algorithms, 62(2):74-92, 2007. Google Scholar
  3. Aaron Bernstein. Maintaining shortest paths under deletions in weighted directed graphs. SIAM Journal on Computing, 45(2):548-574, 2016. Google Scholar
  4. Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, and Norbert Zeh. Approximating geometric bottleneck shortest paths. Computational Geometry, 29(3):233-249, 2004. Google Scholar
  5. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, 1990. Google Scholar
  6. Camil Demetrescu and Giuseppe F Italiano. Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures. Journal of Discrete Algorithms, 4(3):353-383, 2006. Google Scholar
  7. Ran Duan and Seth Pettie. Bounded-leg distance and reachability oracles. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 436-445. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  8. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Twentieth Acm-Siam Symposium on Discrete Algorithms, SODA 2009, New York, Ny, Usa, January, pages 384-391, 2009. Google Scholar
  9. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21-30. ACM, 2015. Google Scholar
  10. Daniel P Martin. Dynamic shortest path and transitive closure algorithms: A survey. arXiv preprint arXiv:1709.00553, 2017. Google Scholar
  11. Liam Roditty and Michael Segal. On bounded leg shortest paths problems. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 775-784. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  12. Tong-Wook Shinn and Tadao Takaoka. Efficient graph algorithms for network analysis. In First International Conference on Resource Efficiency in Interorganizational Networks-ResEff 2013, page 236, 2013. Google Scholar
  13. Tong-Wook Shinn and Tadao Takaoka. Combining all pairs shortest paths and all pairs bottleneck paths problems. In Latin American Symposium on Theoretical Informatics, pages 226-237. Springer, 2014. Google Scholar
  14. Tong-Wook Shinn and Tadao Takaoka. Combining the shortest paths and the bottleneck paths problems. In Proceedings of the Thirty-Seventh Australasian Computer Science Conference-Volume 147, pages 13-18. Australian Computer Society, Inc., 2014. Google Scholar
  15. Tong-Wook Shinn and Tadao Takaoka. Variations on the bottleneck paths problem. Theoretical Computer Science, 575:10-16, 2015. Special Issue on Algorithms and Computation. Google Scholar
  16. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 585-589. ACM, 2007. Google Scholar
  17. Uri Zwick. All pairs shortest paths in weighted directed graphs - exact and almost exact algorithms. In Foundations of Computer Science, 1998. Proceedings. Symposium on, pages 310-319, 1998. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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