Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques

This phenomenon sparked research to understand why these graph techniques are unlikely to help for multi-commodity flow. [Kyng-Zhang'20] reduced solving multi-commodity Laplacians to general linear systems and [Ding-Kyng-Zhang'22] showed that general linear programs can be reduced to 2-commodity flow. However, these reductions create sparse graph instances, so improvement to multi-commodity flows on denser graphs might exist.

In this talk, we will see that one can indeed speed up multi-commodity flow algorithms on non-sparse graphs using graph techniques from single-commodity flow algorithms. This is the first improvement to high accuracy multi-commodity flow algorithms that does not just stem from improvements to general linear program solvers. Using graph data structures based on the celebrated expander decomposition framework, we show that k-commodity flow on an $n$-vertex $m$-edge graph can be solved in $\tilde{O}(k^2.5\sqrt{m}n^{\omega-1/2})$ time for current bounds on fast matrix multiplication $\omega \approx 2.373$.