  Since the development of efficient linear program solvers in the 80s, all
major improvements for solving multi-commodity flows to high accuracy came from
improvements to general linear program solvers. This differs from the single
commodity problem (e.g.~maximum flow) where all recent improvements also rely
on graph specific techniques such as graph decompositions or the Laplacian
paradigm (see e.g.~[CMSV17,KLS20,BLL+21,CKL+22]).
  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, the reductions create sparse graph instances, so improvement to
multi-commodity flows on denser graphs might exist.
  We show 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. In
particular, using graph data structures from recent min-cost flow algorithm by
[BLL+21] based on the celebrated expander decomposition framework, we show that
2-commodity flow on an $n$-vertex $m$-edge graph can be solved in
$\tilde{O}(\sqrt{m}n^{\omega-1/2})$ time for current bounds on fast matrix
multiplication $\omega \approx 2.373$, improving upon the previous fastest
algorithms with $\tilde{O}(m^\omega)$ [CLS19] and $\tilde{O}(\sqrt{m}n^2)$
[KV96] time complexity. For general $k$ commodities, our algorithm runs in
$\tilde{O}(k^{2.5}\sqrt{m}n^{\omega-1/2})$ time.
