Towards (1 + )-approximate flow sparsifiers

DOI10.1137/1.9781611973402.20MaRDI QIDQ5383979zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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)$.

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

Cited in

(19)

• An exponential lower bound for cut sparsifiers in planar graphs
• Network Flow Spanners
• Note: Small integral flows need only sparse networks
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Improved guarantees for vertex sparsification in planar graphs
• The power of vertex sparsifiers in dynamic graph algorithms
• Refined vertex sparsifiers of planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
• Scattering and sparse partitions, and their applications
• Cut sparsification and succinct representation of submodular hypergraphs
• Lower bounds on 0-extension with Steiner nodes
• Optimal padded decomposition for bounded treewidth graphs
• Scattering and sparse partitions, and their applications
• Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms
• Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
• Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs
• Traffic-oblivious multi-commodity flow network design

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)