Topic: Graph Sparsification via Short Cycle Decomposition

Speaker: Sushant Sachdeva

Affiliation: University of Toronto; Member, School of Mathematics

Date & Time: Monday December 9th, 2019, 11:00am - 12:00pm

Location: Simonyi Hall 101

Video: 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