On (1 + ε)-Approximate Flow Sparsifiers

Given a large graph G with a subset |T| = k of its vertices called terminals, a quality-q flow sparsifier is a small graph G⁰ 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,ε) that stores all feasible multicommodity flows up to a factor of (1 + ε), raised the question of constructing quality-(1 + ε) flow sparsifiers whose size only depends on k,ε (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+ε) contraction-based flow sparsifiers with size f(ε) exist for all 5-terminal graphs, but not for 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 spans in metric geometry, which we believe is a powerful tool for future work.