Abstract
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+ϵ) 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. Show more
Publication status
publishedExternal links
Book title
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of ComputingPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
multi-commodity flows; hopsets; flow emulatorsNotes
Conference lecture held on June 24, 2024.More
Show all metadata
ETH Bibliography
yes
Altmetrics