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 factor (1+ ε), raised the question of constructing quality-(1+ ε) 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(ε) 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.