TY - GEN
T1 - Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing
AU - Bernstein, Aaron
AU - Gutenberg, Maximilian Probst
AU - Saranurak, Thatchaphol
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - Let G=(V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source s and the goal is to maintain a data structure that can answer path-queries s rightarrowtail v for any v in V. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to v, and in the SCC problem the goal is to maintain strongly connected components of G and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: They assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 [1] and achieves total update time O(mn). We present the first algorithms to break through this barrier. •deterministic decremental SSR/SSC with total update time mn{2/3+o(1)} •deterministic decremental SSSP with total update time n{2+2/3+o(1)} To achieve these results, we develop two general techniques for working with dynamic graphs. The first generalizes expander-based tools to dynamic directed graphs. While these tools have already proven very successful in undirected graphs, the underlying expander decomposition they rely on does not exist in directed graphs. We thus need to develop an efficient framework for using expanders in directed graphs, as well as overcome several technical challenges in processing directed expanders. We establish several powerful primitives that we hope will pave the way for other expander-based algorithms in directed graphs. The second technique, which we call congestion balancing, provides a new method for maintaining flow under adversarial deletions. The results above use this technique to maintain an embedding of an expander.
AB - Let G=(V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source s and the goal is to maintain a data structure that can answer path-queries s rightarrowtail v for any v in V. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to v, and in the SCC problem the goal is to maintain strongly connected components of G and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: They assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 [1] and achieves total update time O(mn). We present the first algorithms to break through this barrier. •deterministic decremental SSR/SSC with total update time mn{2/3+o(1)} •deterministic decremental SSSP with total update time n{2+2/3+o(1)} To achieve these results, we develop two general techniques for working with dynamic graphs. The first generalizes expander-based tools to dynamic directed graphs. While these tools have already proven very successful in undirected graphs, the underlying expander decomposition they rely on does not exist in directed graphs. We thus need to develop an efficient framework for using expanders in directed graphs, as well as overcome several technical challenges in processing directed expanders. We establish several powerful primitives that we hope will pave the way for other expander-based algorithms in directed graphs. The second technique, which we call congestion balancing, provides a new method for maintaining flow under adversarial deletions. The results above use this technique to maintain an embedding of an expander.
KW - dynamic algorithm
KW - single-source reachability
KW - single-source shortest paths
KW - strongly-connected components
UR - http://www.scopus.com/inward/record.url?scp=85100331502&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100331502&partnerID=8YFLogxK
U2 - 10.1109/FOCS46700.2020.00108
DO - 10.1109/FOCS46700.2020.00108
M3 - Conference contribution
AN - SCOPUS:85100331502
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1123
EP - 1134
BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PB - IEEE Computer Society
T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Y2 - 16 November 2020 through 19 November 2020
ER -