  We study distributed algorithms built around minor-based vertex sparsifiers,
and give the first algorithm in the CONGEST model for solving linear systems in
graph Laplacian matrices to high accuracy. Our Laplacian solver has a round
complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower
bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in
the network and $D$ is its diameter.
  We show that our distributed solver yields new sublinear round algorithms for
several cornerstone problems in combinatorial optimization. This is achieved by
leveraging the powerful algorithmic framework of Interior Point Methods (IPMs)
and the Laplacian paradigm in the context of distributed graph algorithms,
which entails numerically solving optimization problems on graphs via a series
of Laplacian systems. Problems that benefit from our distributed algorithmic
paradigm include exact mincost flow, negative weight shortest paths, maxflow,
and bipartite matching on sparse directed 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. Given that the
hybrid between IPMs and the Laplacian paradigm has proven useful for tackling
numerous optimization problems in the centralized setting, we believe that our
distributed solver will find future applications.
