Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
<|reference_start|>Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs: Flow sparsification is a classic graph compression technique which, given a capacitated graph $G$ on $k$ terminals, aims to construct another capacitated graph $H$, called a flow sparsifier, that preserves, either exactly or approximately, every multicommodity flow between terminals (ideally, with size as a small function of $k$). Cut sparsifiers are a restricted variant of flow sparsifiers which are only required to preserve maximum flows between bipartitions of the terminal set. It is known that exact cut sparsifiers require $2^{\Omega(k)}$ many vertices [Krauthgamer and Rika, SODA 2013], with the hard instances being quasi-bipartite graphs, where there are no edges between non-terminals. On the other hand, it has been shown recently that exact (or even $(1+\varepsilon)$-approximate) flow sparsifiers on networks with just 6 terminals require unbounded size [Krauthgamer and Mosenzon, SODA 2023, Chen and Tan, SODA 2024].   In this paper, we construct exact flow sparsifiers of size $3^{k^{3}}$ and exact cut sparsifiers of size $2^{k^2}$ for quasi-bipartite graphs. In particular, the flow sparsifiers are contraction-based, that is, they are obtained from the input graph by (vertex) contraction operations. Our main contribution is a new technique to construct sparsifiers that exploits connections to polyhedral geometry, and that can be generalized to graphs with a small separator that separates the graph into small components. We also give an improved reduction theorem for graphs of bounded treewidth [Andoni et al., SODA 2011], implying a flow sparsifier of size $O(k\cdot w)$ and quality $O\bigl(\frac{\log w}{\log \log w}\bigr)$, where $w$ is the treewidth.<|reference_end|>
@article{das2024nearly-tight,
    title={Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs},
    author={Syamantak Das, Nikhil Kumar and Daniel Vaz},
    journal={arXiv preprint arXiv:2407.09433},
    year={2024},
    doi={10.4230/LIPIcs.MFCS.2024.45},
    archivePrefix={arXiv},
    eprint={2407.09433},
    primaryClass={cs.DS}
}