Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $\tilde{O}(n^{2/3})$ ¹¹The $\tilde{O}(\cdot)$ notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and $\tilde{O}(m^{3/4})$ time against an adaptive adversary. (2)An incremental data structure that maintains $O(1)$ - approximate shortest path in $n^{o(1)}$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $\tilde{O}(n^{2/3 +o(1)})$ amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an ($1+\epsilon$) factor in $\tilde{O}(n^{2/3+o(1)}\epsilon^{-O(1)})$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as $j$-trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf for the full version of this paper.

I. Introduction

In the study of graph algorithms, there are long-standing gaps in the performances of static and dynamic algorithms. A dynamic graph algorithm is a data structure that maintains a property of a graph that undergoes edge insertions and deletions, with the goal of minimizing the time per update and query operation. Due to the prevalence of large evolving graph data in practice, dynamic graph algorithms have natural connections with network science [1], [2], and databases [3], [4]. However, compared to the wealth of tools available for static graphs, it has proven to be much more difficult to develop algorithms for dynamic graphs, especially fully dynamic ones undergoing both edge insertions and deletions. Even maintaining connectivity undirected graphs has witnessed 35 years of continuous progress [5]–[7]. The directed version, fully dynamic transitive closure, has seen even less progress [8]–[10], and is one of the best reflections of the difficulties of designing dynamic graph algorithms, especially in practice [11].