Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Decremental SSSP in weighted digraphs : Faster and against an adaptive adversary. / Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. red. / Shuchi Chawla. Association for Computing Machinery, 2020. s. 2542-2561.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Decremental SSSP in weighted digraphs
T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
AU - Gutenberg, Maximilian Probst
AU - Wulff-Nilsen, Christian
PY - 2020
Y1 - 2020
N2 - Given a dynamic digraph G = (V, E) undergoing edge deletions and given s ∈ V and constant ǫ with 0 < ǫ ≤ 1, we consider the problem of maintaining (1+ǫ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM'81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC'14, ICALP'15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+o(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ǫ)-approximate data structures: 1. the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, 2. the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time Õ(√mn3/2) for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, 3. the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1+ǫ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.
AB - Given a dynamic digraph G = (V, E) undergoing edge deletions and given s ∈ V and constant ǫ with 0 < ǫ ≤ 1, we consider the problem of maintaining (1+ǫ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM'81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC'14, ICALP'15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+o(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ǫ)-approximate data structures: 1. the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, 2. the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time Õ(√mn3/2) for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, 3. the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1+ǫ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.
UR - http://www.scopus.com/inward/record.url?scp=85084082472&partnerID=8YFLogxK
M3 - Article in proceedings
AN - SCOPUS:85084082472
SP - 2542
EP - 2561
BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
A2 - Chawla, Shuchi
PB - Association for Computing Machinery
Y2 - 5 January 2020 through 8 January 2020
ER -
ID: 250485975