Minor Sparsifiers and the Distributed Laplacian Paradigm

Abstract

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 $\tilde{\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.

arXiv commentAccepted to FOCS 2021. Abstract shortened to respect arXiv's character limit

References in corpus (9)

• A nearly-mlogn time solver for SDD linear systems
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Triangle Finding and Listing in CONGEST Networks
• Distributed Approximation Algorithms for Weighted Shortest Paths
• Faster Divergence Maximization for Faster Maximum Flow
• Sparsified Cholesky Solvers for SDD linear systems
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• Parallel Reachability in Almost Linear Work and Square Root Depth
• Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization

Cited by in corpus (1)

• Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing