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.