Towards (1 + )-approximate flow sparsifiers

DOI10.1137/1.9781611973402.20zbMATH Open1422.68280arXiv1310.3252OpenAlexW4248360301MaRDI QIDQ5383979FDOQ5383979

Authors: Alexandr Andoni, Anupam Gupta, Robert Krauthgamer 

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1310.3252

Recommendations

• Extensions and limits to vertex sparsification
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsifiers: new results from old techniques
• On vertex sparsifiers with Steiner nodes
• Network Flow Spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Flows in graphs (05C21)

Cited In (8)

• An exponential lower bound for cut sparsifiers in planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Network Flow Spanners
• The power of vertex sparsifiers in dynamic graph algorithms
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs

This page was built for publication: Towards \((1 + \varepsilon)\)-approximate flow sparsifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383979)