Faster Distributed Graph Algorithms via Continuous Optimization Methods

Graph problems have been widely researched and possess a broad class of applications. The increasing large-scale graphs in various applications have necessitated the development of distributed algorithms. Inspired by the successful applications of continuous optimization methods in improving some combinatorial optimization problems, we adapt the sequential optimization approaches to distributed settings and enhance the current distributed graph problems. As a foundational component of these work, the Laplacian solver plays a vital role. Although the Laplacian solver has undergone comprehensive investigation in both sequential and parallel models, it remains open how to design an efficient distributed Laplacian solver. In this thesis, we close this gap by extending Laplacian paradigm to distributed settings. Firstly, we employ preconditioned conjugate gradient method, and combine a distributed spectral approximation algorithm with a distributed Laplacian solver developed for sparse graphs, achieving an ${O}(n^{1/4 + o(1)} (\sqrt{n} + D))$-round algorithm in the \congest model, where $n$ and $D$ are the number of vertices and the diameter of the communication network, respectively. Then we further improve the round complexity to $O(n^{o(1)} (\sqrt{n}+D))$, which almost matches its lower bound $\wt{\Omega}(\sqrt{n}+D)$, by combining the developed distributed spectral subspace sparsifier with both tree and elimination-based preconditioners. Armed with the distributed Laplacian solver, we obtain the first exact sublinear-round distributed algorithms for maximum flow, min-cost flow, and single-source shortest path (SSSP) on sparse graphs by simulating the existingly sequential algorithms. The distributed algorithms we have developed above are designed for worst-case scenarios which correspond to a family of pathological networks. However, it is important to note that these worst-case conditions may not be applicable to the majority of networks encountered in practice. As a result, we employ an alternative concept to quantify the round complexity, namely, the optimal round complexity of the correct algorithms on graph $G$. We illustrate the SSSP problem as a concrete example. Our primary technique involves using low-diameter decompositions to construct the first efficient $n^{o(1)}$-competitive linear $\ell_1$-oblivious routing operator, which is much simpler than existing methods. Then combining this $\ell_1$-oblivious routing with boosting property for transshipment, we give the first universally-optimal distributed algorithm for $(1 + \eps)$-approximate SSSP.