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. - 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. We utilize these decompositions to prove several new results in graph sparsification: And more. This is joint works with Timothy Chu, Yu Gao, Yang Liu, Richard Peng, Saurabh Sawlani, Junxing Wang, and Zejun Yu.