Faster Min-Cost Flow on Bounded Treewidth Graphs

We present a $\widetilde{O}(m\sqrt{\tau}+n\tau)$ time algorithm for finding a minimum-cost flow in graphs with $n$ vertices and $m$ edges, given a tree decomposition of width $\tau$ and polynomially bounded integer costs and capacities. This improves upon the current best algorithms for general linear programs bounded by treewidth which run in $\widetilde{O}(m \tau^{(\omega+1)/2})$ time by [Dong-Lee-Ye,21] and [Gu-Song,22], where $\omega \approx 2.37$ is the matrix multiplication exponent. Our approach leverages recent advances in structured linear program solvers and robust interior point methods. As a corollary, for any graph $G$ with $n$ vertices, $m$ edges, and treewidth $\tau$, we obtain a $\widetilde{O}(\tau^3 \cdot m)$ time algorithm to compute a tree decomposition of $G$ with width $O(\tau \cdot \log n)$.