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.