We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decompositiona decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2 log n, and at most 2n extra edges. We give an m 1+o(1) time algorithm for constructing a short cycle decomposition, with cycles of length n o(1) , and n 1+o(1) extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1) We present an algorithm that runs in time m 1+o(1) ε −1.5 and returns (1 ± ε)-approximations to effective resistances of all edges, improving over the previous best of O(min{mε −2 , n 2 ε −1 }). This routine in turn gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± ε) in m 1+o(1) + n 15/8+o(1) ε −7/4 time. 2) We show existence and efficient algorithms for constructing graphical spectral sketches -a distribution over graphs H with about nε −1 edges such that for a fixed vector x , we have x LH x = (1 ± ε)x LGx and x L + H x = (1±ε)x L + G x with high probability, where L is the graph Laplacian and L + is its pseudoinverse. This implies the existence of resistance-sparsifiers with about nε −1 edges that preserve the effective resistances between every pair of vertices up to (1 ± ε). 3) By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of Eulerian directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for constructing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms. Due to space constraints, most of the proofs are deferred to the full version [1] available at http://arxiv.org/abs/1805.12051. Restricting the above definition only to vectors x ∈ {±1} V , one obtains cut sparsifiers. For a graph G with n vertices and m edges, Spielman and Teng gave the first algorithm for constructing spectral sparsifiers with O(nε −2 ) edges 1 . Spielman and Srivastava [15] proved that one could construct a sparsifier for G by independently sampling O(nε −2 log n) edges with probabilities proportional to their leverage scores in G. Finally, Batson, Spielman, and Srivastava [16] proved 1 The O(·) notation hides poly(log n) factors.
REF presents an algorithm that computes the effective resistances of all edges to (1 ± )-errors in O(m 1+o(1) −1.5 ) time.
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
Computer Science Mathematics