Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

05/05/2020
by   Li Chen, et al.
0

We present a general framework of designing efficient dynamic approximate algorithms for optimization 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 Õ(n^2/3) amortized time against an oblivious adversary, and Õ(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 Õ(n^2/3+o(1)) amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+ϵ) factor in Õ(n^2/3+o(1)ϵ^-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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset