Short Cycles via Low-Diameter Decompositions

We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress on several questions in graph sparsification. For all constants δ ∈ (0,1], we give an O(mnδ) time algorithm that, given a graph G, partitions its edges into cycles of length O(log n)^frac1δ, with O(n) extra edges not in any cycle. This gives the first subquadratic, in fact almost linear time, algorithm achieving polylogarithmic cycle lengths. We also give an m · exp(O(√log n)) time algorithm that partitions the edges of a graph into cycles of length exp(O(√log n loglog n)), with O(n) extra edges not in any cycle. This improves on the short cycle decomposition algorithms given in Chu et al in terms of all parameters, and is significantly simpler. As a result, we obtain faster algorithms and improved guarantees for several problems in graph sparsification -- construction of resistance sparsifiers, graphical spectral sketches, degree preserving sparsifiers, and approximating the effective resistances of all edges.