Duan, Ran ;
Ren, Hanlin
Approximating AllPair BoundedLeg Shortest Path and APSPAF in TrulySubcubic Time
Abstract
In the boundedleg 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 APSPAF (allpair 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 APSPAF 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 trulysubcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time maxmin product algorithm [Duan and Pettie 2009]. Since the allpair bottleneck path (APBP) problem, which is equivalent to maxmin product, can be seen as allpair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.
BibTeX  Entry
@InProceedings{duan_et_al:LIPIcs:2018:9046,
author = {Ran Duan and Hanlin Ren},
title = {{Approximating AllPair BoundedLeg Shortest Path and APSPAF in TrulySubcubic Time}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {42:142:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9046},
URN = {urn:nbn:de:0030drops90467},
doi = {10.4230/LIPIcs.ICALP.2018.42},
annote = {Keywords: Graph Theory, Approximation Algorithms, Combinatorial Optimization}
}
04.07.2018
Keywords: 

Graph Theory, Approximation Algorithms, Combinatorial Optimization 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 