Low-Step Multi-Commodity Flow Emulators
<|reference_start|>Low-Step Multi-Commodity Flow Emulators: We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.   We prove the existence of low-step multi-commodity flow emulators and develop efficient algorithms to compute them. We then apply them to solve constant-approximate $k$-commodity flow in $O((m+k)^{1+\epsilon})$ time. To bypass the $O(mk)$ flow decomposition barrier, we represent our output multi-commodity flow implicitly; prior to our work, even the existence of implicit constant-approximate multi-commodity flows of size $o(mk)$ was unknown.   Our results generalize to the minimum cost setting, where each edge has an associated cost and the multi-commodity flow must satisfy a cost budget. Our algorithms are also parallel.<|reference_end|>
@article{haeupler2024low-step,
    title={Low-Step Multi-Commodity Flow Emulators},
    author={Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe,
  Thatchaphol Saranurak},
    journal={arXiv preprint arXiv:2406.14384},
    year={2024},
    doi={10.1145/3618260.3649689},
    archivePrefix={arXiv},
    eprint={2406.14384},
    primaryClass={cs.DS}
}