Algorithms Seminar

On (1+\eps)-Approximate Flow Sparsifiers

October 12, -
Speaker(s): Zihan Tan


Given a large graph G with a subset |T|=k of its vertices called terminals, a quality-q flow sparsifier is a small graph H that contains T and preserves all multicommodity flows that can be routed between terminals in T, to within factor q. The problem of constructing flow sparsifiers with good (small) quality and (small) size has been a central problem in graph compression for decades.

A natural approach of constructing O(1)-quality flow sparsifiers, which was adopted in most previous constructions, is contraction. Andoni, Krauthgamer, and Gupta constructed a sketch of size f(k,\eps) that stores all feasible multicommodity flows up to factor (1+\eps), raised the question of constructing quality-(1+\eps) flow sparsifiers whose size only depends on k,\eps (but not the number of vertices in the input graph G), and proposed a contraction-based framework towards it using their sketch result. In this paper, we settle their question for contraction-based flow sparsifiers, by showing that quality-(1+\eps) contraction-based flow sparsifiers with size f(\eps) exist for all 5-terminal graphs, but not all 6-terminal graphs. Our hardness result on 6-terminal graphs improves upon a recent hardness result by Krauthgamer and Mosenzon on exact (quality-1) flow sparsifiers, for contraction-based constructions. Our construction and proof utilize the notion of tight span in metric geometry.

This talk is based on joint work with Yu Chen.


Currently a postdoctoral student at DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University, Zihan Tan obtained his PhD from University of Chicago. He is broadly interested in theoretical computer science, with his research focusing on designing algorithms and proving lower bounds for combinatorial optimization problems. He is currently working on problems in graph theory and graph algorithms.


LSRC D344 or join virtually via Zoom


Yiheng Shen