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 & 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