Computer Science Theory Seminar
Zihan Tan
Rutgers
On (1+$\eps$)-Approximate Flow Sparsifiers
Abstract: 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.
Wednesday October 18, 2023 at 12:00 PM in 712 SEO