TY - GEN

T1 - Maintaining shortest paths under deletions in weighted directed graphs

AU - Bernstein, Aaron

PY - 2013

Y1 - 2013

N2 - We present an improved algorithm for maintaining all-pairs (1 + ε) approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem was total update time O ̃(n 2√m/ε) for directed, unweighted graphs [2], and Õ(mn=ε) for undirected, unweighted graphs [12]. Both algorithms were randomized and had constant query time. Note that Õ(mn) is a natural bar- rier because even with a (1 + ε) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs short- est path problem. Our algorithm works on directed, weighted graphs and has total (randomized) update time Õ(mnlog(R)=ε) where R is the ratio of the largest edge weight ever seen in the graph, to the smallest such weight (our query time is constant). Note that log(R) = O(log(n)) as long as weights are poly- nomial in n. Although Õ(mnlog(R)=ε) is the total time over all updates, our algorithm also requires a clearly unavoid- able constant time per update. Thus, we effectively expand the Õ (mn) total update time bound from undirected, un- weighted graphs to directed graphs with polynomial weights. This is in fact the first non-trivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (pre- vious algorithms could only handle small integer weights). By a well known reduction from decremental algorithms to fully dynamic ones [9], our improved decremental algorithm leads to improved query-update tradeoffs for fully dynamic (1 + ε) approximate APSP algorithm in directed graphs.

AB - We present an improved algorithm for maintaining all-pairs (1 + ε) approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem was total update time O ̃(n 2√m/ε) for directed, unweighted graphs [2], and Õ(mn=ε) for undirected, unweighted graphs [12]. Both algorithms were randomized and had constant query time. Note that Õ(mn) is a natural bar- rier because even with a (1 + ε) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs short- est path problem. Our algorithm works on directed, weighted graphs and has total (randomized) update time Õ(mnlog(R)=ε) where R is the ratio of the largest edge weight ever seen in the graph, to the smallest such weight (our query time is constant). Note that log(R) = O(log(n)) as long as weights are poly- nomial in n. Although Õ(mnlog(R)=ε) is the total time over all updates, our algorithm also requires a clearly unavoid- able constant time per update. Thus, we effectively expand the Õ (mn) total update time bound from undirected, un- weighted graphs to directed graphs with polynomial weights. This is in fact the first non-trivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (pre- vious algorithms could only handle small integer weights). By a well known reduction from decremental algorithms to fully dynamic ones [9], our improved decremental algorithm leads to improved query-update tradeoffs for fully dynamic (1 + ε) approximate APSP algorithm in directed graphs.

KW - Approximation algorithms

KW - Dynamic algorithms

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=84879832594&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879832594&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488701

DO - 10.1145/2488608.2488701

M3 - Conference contribution

AN - SCOPUS:84879832594

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 725

EP - 734

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -