Abstract
We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals T of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of electrical flows between the terminals in T. We give a data structure that supports insertions and deletions of edges, and terminal additions, all in sublinear time. We then show the applicability of our result to the following problems.
(1) A data structure for dynamically maintaining solutions to Laplacian systems L x = b, where L is the graph Laplacian matrix and b is a demand vector. For a bounded degree, unweighted graph, we support modifications to both L and b while providing access to є-approximations to the energy of routing an electrical flow with demand b, as well as query access to entries of a vector x such that ∥x−L† b ∥L ≤ є ∥L† b ∥L in Õ(n11/12є−5) expected amortized update and query time.
(2) A data structure for maintaining fully dynamic All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structures returns (1 ± є)-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are Õ(min(m3/4,n5/6 є−2) є−4) on an unweighted graph, and Õ(n5/6є−6) on weighted graphs.
The key ingredients in these results are (1) the intepretation of Schur complement as a sum of random walks, and (2) a suitable choice of terminals based on the behavior of these random walks to make sure that the majority of walks are local, even when the graph itself is highly connected and (3) maintenance of these local walks and numerical solutions using data structures.
These results together represent the first data structures for maintain key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies. The importance of routines such as effective resistance, electrical flows, and Laplacian solvers in the static setting make us optimistic that some of our components can provide new building blocks for dynamic graph algorithms.
