Lower Bounds on Flow Sparsifiers with Steiner Nodes

Given a large graph G with a set of its k vertices called terminals, a quality-q flow sparsifier is a small graph G ′ that contains the terminals and preserves all multicommodity flows between them up to some multiplicative factor q ≥ 1, called the quality. Constructing flow sparsifiers with good quality and small size (|V(G ′ )|) has been a central problem in graph compression.

The most common approach of constructing flow sparsifiers is contraction: first compute a partition of the vertices in V(G), and then contract each part into a supernode to obtain G ′ . When G ′ is only allowed to contain all terminals, the best quality is shown to be O(log k/ log log k) and Ω( log k/ log log k). In this paper, we show that allowing a few Steiner nodes does not help much in improving the quality. Specifically, there exist k-terminal graphs such that, even if we allow k • 2 (log k) Ω(1) Steiner nodes in its contraction-based flow sparsifier, the quality is still Ω (log k) 0.3 .