Exact Flow Sparsification Requires Unbounded Size

Robert Krauthgamer, Ron Mosenzon

Given a large edge-capacitated network $G$ and a subset of $k$ vertices called terminals, an (exact) flow sparsifier is a small network $G^{\prime }$ that preserves (exactly) all multicommo…