Minor Sparsifiers and the Distributed Laplacian Paradigm

We study distributed algorithms built around edge contraction based vertex sparsifiers, and give sublinear round algorithms in the $\textsf{CONGEST}$ model for exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. These algorithms follow the celebrated Laplacian paradigm, which numerically solve combinatorial graph problems via series of linear systems in graph Laplacian matrices. To enable Laplacian based algorithms in the distributed setting, we develop a Laplacian solver based upon the subspace sparsifiers of [Li, Schild FOCS'18]. We give a parallel variant of their algorithm that avoids the sampling of random spanning trees, and analyze it using matrix martingales. Combining this vertex reduction recursively with both tree and elimination based preconditioners leads to an algorithm for solving Laplacian systems on $n$ vertex graphs to high accuracy in $O(n^{o(1)}(\sqrt{n}+D))$ rounds. The round complexity of this distributed solver almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$.