2026-07-23T20:55:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9046 2024-03-06T10:43:14Z ddc:004 open_access

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time Duan, Ran Ren, Hanlin Graph Theory Approximation Algorithms Combinatorial Optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Duan and Hanlin Ren 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.42 urn:nbn:de:0030-drops-90467 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.42 eng https://creativecommons.org/licenses/by/3.0/legalcode