On (1 + ɛ)-Approximate Flow Sparsifiers
Yu Chen, Zihan Tan · Society for Industrial and Applied Mathematics eBooks · 2024
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.