2020/11/10 by Sally Dong, Yin Tat Lee, Dong, Sally +3 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2011.05365
Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms in various communities including combinatorics, integer-linear programming, and numerical analysis. Many NP-hard problems are known to be solvable in \widetildeO(n ⋅ 2O(tw)) time, where tw is the treewidth of the input graph. Analogously, many problems in P should be solvable in \widetildeO(n ⋅ twO(1)) time; however, due to the lack of appropriate tools, only a few such results are currently known. [Fom+18] conjectured this to hold as broadly as all linear programs; in our paper, we show this is true: Given a linear program of the form minAx=b,ℓ ≤ x≤ u c\top x, and a width-τ tree decomposition of a graph GA related to A, we show how to solve it in time \widetildeO(n ⋅ τ2 log (1/ε)), 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 \widetildeO(n1+o(1) ⋅ tw2 log (1/ε)) run-time. 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). 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.