Extensions and limits to vertex sparsification

Suppose we are given a graph G = (V, E) and a set of terminals K ⊂ V. We consider the problem of constructing a graph H = (K, E_H) that approximately preserves the congestion of every multicommodity flow with endpoints supported in K. We refer to such a graph as a flow sparsifier. We prove that there exist flow sparsifiers that simultaneously preserve the congestion of all multicommodity flows within an O(log k / log log k)-factor where |K| = k. This bound improves to O(1) if G excludes any fixed minor. This is a strengthening of previous results, which consider the problem of finding a graph H = (K, E_H) (a cut sparsifier) that approximately preserves the value of minimum cuts separating any partition of the terminals. Indirectly our result also allows us to give a construction for better quality cut sparsifiers (and flow sparsifiers). Thereby, we immediately improve all approximation ratios derived using vertex sparsification in [14].

We also prove an Ω(log log k) lower bound for how well a flow sparsifier can simultaneously approximate the congestion of every multicommodity flow in the original graph. The proof of this theorem relies on a technique (which we refer to as oblivious dual certifcates) for proving super-constant congestion lower bounds against many multicommodity flows at once. Our result implies that approximation algorithms for multicommodity flow-type problems designed by a black box reduction to a "uniform" case on k nodes (see [14] for examples) must incur a super-constant cost in the approximation ratio.