Zihan Tan : On (1+$\eps$)-Approximate Flow Sparsifiers

Posted by Karoline Dubin , part of the Computer Science Theory Seminar.

At

Oct. 18, 2023, noon

In

712 SEO

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.