Graph Sparsification via Short Cycle Decomposition

Computer Science/Discrete Mathematics Seminar I
Topic:Graph Sparsification via Short Cycle Decomposition
Speaker:Sushant Sachdeva
Affiliation:University of Toronto; Member, School of Mathematics
Date:Monday, December 9
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/1209-SushantSachdeva

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