Towards (1 + ∊)-Approximate Flow Sparsifiers

<p>A useful approach to “compress” a large network <em>G</em> is to represent it with a <em>flow-sparsifier</em>, i.e., a small network <em>H</em> that supports the same flows as <em>G</em>, up to a factor <em>q</em> ≥ 1 called the quality of sparsifier. Specifically, we assume the network <em>G</em> contains a set of <em>k</em> terminals <em>T</em>, shared with the network <em>H</em>, i.e., <em>T</em> ⊆ <em>V</em>(<em>G</em>)∩<em>V</em>(<em>H</em>), and we want <em>H</em> to preserve all multicommodity flows that can be routed between the terminals <em>T</em>. The challenge is to construct <em>H</em> that is small.</p> <p>These questions have received a lot of attention in recent years, leading to some known tradeoffs between the sparsifier's quality <em>q</em> and its size |<em>V</em>(<em>H</em>)|. Nevertheless, it remains an outstanding question whether every <em>G</em> admits a flow-sparsifier <em>H</em> with quality <em>q</em> = 1 + <em>∊</em>, or even <em>q</em> = <em>O</em>(1), and size |<em>V</em>(<em>H</em>)| <em>≤ f</em>(<em>k, ∊</em>) (in particular, independent of |<em>V</em>(<em>G</em>)| and the edge capacities).</p> <p>Making a first step in this direction, we present new constructions for several scenarios:</p> <ul> <li> <p>Our main result is that for quasi-bipartite networks <em>G</em>, one can construct a (1 + <em>∊</em>)-flow-sparsifier of size poly(<em>k</em>/<em>∊</em>). In contrast, exact (<em>q</em> = 1) sparsifiers for this family of networks are known to require size 2^{<em>Ω</em>(<em>k</em>)}.</p> </li> <li> <p>For networks <em>G</em> of bounded treewidth <em>w</em>, we construct a flow-sparsifier with quality <em>q</em> = <em>O</em>(log<em>w</em>/loglog<em>w</em>) and size <em>O</em>(<em>w</em>·poly(<em>k</em>)).</p> </li> <li> <p>For general networks <em>G</em>, we construct a <em>sketch sk</em>(<em>G</em>), that stores all the feasible multicommodity flows up to factor <em>q</em> = 1 + <em>∊</em>, and its size (storage requirement) is <em>f</em>(<em>k, ∊</em>).</p> </li> </ul>