אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Graphs are often too complex to handle directly, so a recurring theme in graph algorithms is to replace them by simpler objects that approximately preserve the quantities we care about. In this talk, I will discuss one particularly clean form of graph sparsification: tree sparsifiers. A tree cut-sparsifier replaces a capacitated graph by a single tree that approximately preserves every cut, while a tree flow-sparsifier gives a tree whose routable demands can be transferred back to the original graph with bounded congestion.

I will start with the classical line of work on tree sparsifiers. I will then present our improved construction for tree sparsifiers in near-linear time. For an undirected capacitated graph on n vertices, our algorithm constructs a tree cut-sparsifier of quality O(log^2 n log log n), nearly matching the best known polynomial-time quality. Via the flow-cut gap, this also yields a tree flow-sparsifier with congestion approximation O(log^3 n log log n).

A key feature of the construction is that it is highly modular. We combine previous ideas in tree sparsification with recent advances in expander decomposition, using the latter almost as a black box. This viewpoint lets us simplify the structure of earlier constructions, improve their guarantees, and implement a "refinement phase" in near-linear time.

 Based on a joint work with Daniel Agassy and Haim Kaplan.