Graph Sparsification via Short Cycle Decomposition

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a 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 almost-linear time algorithm for constructing a short cycle decomposition, with sub-polynomial n^o(1) cycle length, and almost-linear number of extra edges.

We utilize these decompositions to prove several new results in graph sparsification:

- Existence and efficient construction of a spectral sparsifier of a graph that exactly preserve original vertex degrees

- Existence and efficient construction of ‘resistance sparsifiers’ -- very sparse graphs that approximately preserve effective resistances between all pairs of vertices of the original graph

- Computing effective resistances of all edges in a graph, and approximating the number of spanning trees in a graph in the fastest known time.

And more.

This is joint works with Timothy Chu, Yu Gao, Yang Liu, Richard Peng, Saurabh Sawlani, Junxing Wang, and Zejun Yu.



University of Toronto; Member, School of Mathematics