A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path

Arising from structural graph theory, treewidth has become a focus of study in fixedparameter tractable algorithms in various communities including combinatorics, integer-linear programming, and numerical analysis. Many NP-hard problems are known to be solvable in O(n • 2 O(tw) ) time, where tw is the treewidth of the input graph. Analogously, many problems in P should be solvable in O(n • tw O(1) ) time; however, due to the lack of appropriate tools, only a few such results are currently known. [FLS + 18] conjectured this to hold for as broadly as all linear programs; in our paper, we show this is true: Given a linear program of the form min Ax=b,ℓ⩽x⩽u c ⊤ x, and a width-τ tree decomposition of a graph G A related to A, we show how to solve it in time where n is the number of variables and ε is the relative accuracy. Combined with recent techniques in vertex-capacitated flow [BGS21], this leads to an algorithm with O(n 1+o(1) • tw 2 log(1/ε)) runtime. Besides being the first of its kind, our algorithm has runtime nearly matching the fastest runtime for solving the sub-problem Ax = b, under the assumption that no fast matrix multiplication is used. We obtain these results by combining recent techniques in interior-point methods (IPMs), sketching, and a novel representation of the solution under a multiscale basis similar to the wavelet basis.