  We present an algorithm for min-cost flow in graphs with $n$ vertices and $m$
edges, given a tree decomposition of width $\tau$ and size $S$, and
polynomially bounded, integral edge capacities and costs, running in
$\widetilde{O}(m\sqrt{\tau} + S)$ time. This improves upon the previous fastest
algorithm in this setting achieved by the bounded-treewidth linear program
solver by [Dong-Lee-Ye,21] and [Gu-Song,22], which runs in $\widetilde{O}(m
\tau^{(\omega+1)/2})$ time, 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 (IPM). For general
graphs where treewidth is trivially bounded by $n$, the algorithm runs in
$\widetilde{O}(m \sqrt n)$ time, which is the best-known result without using
the Lee-Sidford barrier or $\ell_1$ IPM, demonstrating the surprising power of
robust interior point methods.
  As a corollary, we obtain a $\widetilde{O}(\operatorname{tw}^3 \cdot m)$ time
algorithm to compute a tree decomposition of width $O(\operatorname{tw}\cdot
\log(n))$, given a graph with $m$ edges.
