Fully Dynamic Spectral Vertex Sparsifiers and Applications

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. Our result is then applied to the following problems. (1) A data structure for maintaining solutions to Laplacian systems L x = b, where L is the 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 tildex such that leftlVert tildex-Ldagger b rightrVertL ≤ ε leftlVert Ldagger b rightrVertL in tildeO(n11/12ε-5) expected amortized update and query time. (2) A data structure for maintaining All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structure returns (1 ± ε)-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are tildeO(min(m3/4,n5/6 ε-2) ε-4) on an unweighted graph, and tildeO(n5/6ε-6) on weighted graphs. These results represent the first data structures for maintaining key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies.