Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

Abstract

We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs - a decomposition of a graph into a 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+o(1)</sup> time algorithm for constructing a short cycle decomposition of the graph, with cycles of length n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(1)</sup> , and n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+o(1)</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+o(1)</sup> ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1.5</sup> and returns (1 ± ε)-approximations to effective resistances of all edges, improving over the previous best of Õ(min{mε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-2</sup> , n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> }) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± ε) in roughly m + n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">15/8</sup> ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-7/4</sup> . 2. We show existence and efficient algorithms for constructing graphical spectral sketches - a distribution over sparse graphs H with about nε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> edges such that for a fixed vector x, we have x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</sub> x = (1 ± eps) x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub> x and x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> L+ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</sub> x = (1 ± ε) x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> L+ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub> x with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about nε edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for directed random walks and linear systems in directed Laplacian. 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 producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.