Before revision:  Combined with existing techniques in vertex separators  , this leads to algorithms with O(n \cdot tw ^4 \log (1/\varepsilon)) and (n \cdot \mathrm{tw ^2 \log (1/\varepsilon) + n^{1.5 . Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem Ax=b (under the assumption that no fast matrix multiplication is used).
After revision:  Combined with recent techniques in vertex-capacitated flow , this leads to algorithms with O(n \cdot tw ^4 \log (1/\varepsilon)) and (n \cdot \mathrm{tw ^2 \log (1/\varepsilon) + n^{1.5 . Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem Ax=b (under the assumption that no fast matrix multiplication is used).