Fully dynamic spectral vertex sparsifiers and applications

DOI10.1145/3313276.3316379MaRDI QIDQ5212832zbMATH OpenOpenAlexFDO

Authors David Durfee, Yu Gao, Gramoz Goranci, Richard Peng

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.10530

zbMATH Keywords

dynamic graph algorithmseffective resistancegraph LaplacianSchur complement

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Applications of graph theory to circuits and networks (94C15)

Abstract: We study emph{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 $mathbfLmathbfx=mathbfb$, where $mathbfL$ is the Laplacian matrix and $mathbfb$ is a demand vector. For a bounded degree, unweighted graph, we support modifications to both $mathbfL$ and $mathbfb$ while providing access to $epsilon$-approximations to the energy of routing an electrical flow with demand $mathbfb$, as well as query access to entries of a vector $ildemathbfx$ such that $leftlVertildemathbfx-mathbf{L}^{dagger}mathbfbightVer{t}_{mathbfL}leqepsilonleftlVertmathbf{L}^{dagger}mathbfbightVer{t}_{mathbfL}$ in $ildeO(n^{11/12}epsilo{n}^{-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 $(1pmepsilon)$-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are $ildeO(min(m^{3/4},n^{5/6}epsilo{n}^{-2})epsilo{n}^{-4})$ on an unweighted graph, and $ildeO(n^{5/6}epsilo{n}^{-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.

Recommendations

• The power of vertex sparsifiers in dynamic graph algorithms
• Graph sparsification by effective resistances
• Spectral sparsification in dynamic graph streams
• Single pass spectral sparsification in dynamic streams
• Sparsification—a technique for speeding up dynamic graph algorithms

Cited in

(9)

• Sublinear update time randomized algorithms for dynamic graph regression
• Dynamic effective resistances and approximate Schur complement on separable graphs
• The power of vertex sparsifiers in dynamic graph algorithms
• Vertex Sparsifiers: New Results from Old Techniques
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• Fast leader selection for opinion maximization in signed graphs
• Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs
• Incremental approximate maximum flow via residual graph sparsification
• Incremental approximate maximum flow via residual graph sparsification

This page was built for publication: Fully dynamic spectral vertex sparsifiers and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212832)