Source-linked AI summary
Distributed Approximation Algorithms for Weighted Shortest Paths
Danupon Nanongkai
TL;DR
The paper studies weighted shortest-path approximation in bandwidth-limited distributed networks, where algorithms have faced a trade-off between running time and approximation quality. It combines bounded-hop multi-source shortest paths with reductions to overlay networks. The resulting algorithms give near-optimal SSSP and APSP guarantees, while small-diameter networks attain the lower-bound SSSP time up to polylogarithmic factors.
Problem
The paper seeks algorithms for weighted distributed shortest paths that achieve both small approximation guarantees and small running times.
Method
The approach combines bounded-hop multi-source shortest paths with a reduction from SSSP on the original network to SSSP on a landmark or skeleton overlay network.
Results
˜O(n1/2D1/4 + D) rounds give a (1 + o(1))-approximation for SSSP, while ˜O(n) rounds give a (1 + o(1))-approximation for APSP.
Takeaways & Limitations
When D is small, the SSSP running time matches the ˜Ω(n1/2 + D) lower bound up to a polylogarithmic factor.
Takeaways & Limitations
The paper leaves open closing the gap between the ˜O(n1/2D1/4) upper bound and the ˜Ω(n1/2) lower bound for (1 + ϵ)-approximate SSSP on general networks.
Abstract
from arXiv · showhide
A distributed network is modeled by a graph having $n$ nodes (processors) and diameter $D$. We study the time complexity of approximating {\em weighted} (undirected) shortest paths on distributed networks with a $O(\log n)$ {\em bandwidth restriction} on edges (the standard synchronous \congest model). The question whether approximation algorithms help speed up the shortest paths (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (\sssp) and all-pairs shortest paths (\apsp) in the weighted case. Our main result is an algorithm for \sssp. Previous results are the classic $O(n)$-time Bellman-Ford algorithm and an $\tilde O(n^{1/2+1/2k}+D)$-time $(8k\lceil \log (k+1) \rceil -1)$-approximation algorithm, for any integer $k\geq 1$, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use $\tilde O(\cdot)$ to hide the $O(\poly\log n)$ term.) We present an $\tilde O(n^{1/2}D^{1/4}+D)$-time $(1+o(1))$-approximation algorithm for \sssp. This algorithm is {\em sublinear-time} as long as $D$ is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When $D$ is small, our running time matches the lower bound of $\tilde Ω(n^{1/2}+D)$ by Das Sarma et al. (SICOMP 2012), which holds even when $D=Θ(\log n)$, up to a $\poly\log n$ factor.
1 Introduction
The paper addresses whether weighted shortest paths can be approximated quickly in bandwidth-limited distributed networks, targeting both small approximation guarantees and sublinear running times. It gives near-optimal SSSP and APSP algorithms, with tightness results and especially strong guarantees on small-diameter or fully connected networks.
- Introduction: The work targets a longstanding open question: whether approximation can speed up distributed shortest-path computation without requiring a large approximation factor.Earlier sublinear SSSP and linear APSP algorithms required high approximation guarantees.
- Problems & Definitions: The model restricts each edge to O(log n)-bit messages per synchronous round, with edge weights drawn from {1, 2, ..., poly(n)}.Each edge weight is known only to its endpoints and can be transmitted in one round under the polynomial-weight assumption.
- Our Results: ˜O(n1/2D1/4 + D) rounds suffice for a (1 + o(1))-approximation to weighted SSSP on general networks.The algorithm is sublinear whenever D is sublinear in n.
- Our Results: When D is small, the SSSP running time matches the ˜Ω(n1/2 + D) lower bound up to polylogarithmic factors.The lower bound holds even for algorithms with poly(n) approximation ratios and applies in the quantum setting as well.
- Our Results: ˜O(n) rounds suffice for a (1 + o(1))-approximation to weighted APSP on general networks.The paper also proves an APSP lower bound matching this running time up to polylogarithmic factors.
- Our Results: For fully connected networks, ˜O(n1/2) rounds yield exact SSSP and a (2 + o(1))-approximation for APSP.Fully connected networks have diameter D = 1 and include overlay and peer-to-peer settings.
2 Overview
The overview develops two tools for distributed weighted shortest paths: a light-weight bounded-hop SSSP algorithm and shortest-path diameter reduction using shortcuts. These tools yield sublinear or near-linear algorithms for SSSP and APSP in general and fully-connected networks.
- Tool 1: Light-Weight Bounded-Hop SSSP: The light-weight bounded-hop method rounds edge weights and applies BFS across multiple weight scales, preserving near-unit approximation.Weight rounding makes the relevant path weights O(h/ϵ), while BFS remains light-weight because it sends at most one message per edge.
- Tool 2: Shortest-Path Diameter Reduction Using Shortcuts: Adding shortcuts from every node to its k nearest nodes, weighted by exact distances, reduces the shortest-path diameter to O(n/k).This construction is nontrivial because it uses only k nearest nodes rather than all nodes within k hops, and it applies to undirected graphs.
- APSP and Fully-Connected Networks: ˜O(n) time suffices for (1+o(1))-approximate APSP on general networks by running the bounded-hop tool from every node as a source.On fully-connected networks, the overview also describes exact SSSP using n1/2 shortcuts and a (2+o(1))-approximate APSP algorithm using both tools.
- SSSP on General Networks: ˜O(n1/2D1/4 + D) time suffices for (1+o(1))-approximate SSSP on general networks.The algorithm combines approximate h-hop distances, a sampled intermediate set, and the light-weight SSSP simulation.
3 Main Tools
The section develops two lightweight tools for weighted shortest-path computation: bounded-hop SSSP that supports parallel multi-source execution, and shortcuts that reduce shortest-path diameter.
- Lightweight bounded-hop SSSP: (1 + o(1))-approximate h-hop SSSP runs in ˜O(h + D) time while each node broadcasts only O(log n) polylogarithmic-size messages.This lightweight communication pattern makes the bounded-hop procedure suitable for parallelization.
- Lightweight bounded-hop SSSP: The bounded-hop method approximates weights across O(log n) scales and combines bounded-distance SSSP results to recover h-hop distances.Each node locally computes scaled edge weights, then executes bounded-distance SSSP for each scale.
- Lightweight bounded-hop SSSP: The bounded-hop SSSP procedure runs for K rounds and makes each node broadcast once per reached distance, yielding O(log n) broadcasts across all weight scales.The bounded-distance routine is a modification of a standard breadth-first tree algorithm.
- Bounded-hop MSSP: (1 + o(1))-approximate k-source h-hop shortest paths can be computed in ˜O(k + h + D) time by running bounded-hop SSSP instances in parallel.Random delays control congestion when messages from multiple source executions overlap.
- Shortest-path diameter reduction: Shortcuts augment the graph with edges to reduce its shortest-path diameter.The k-shortcut graph has shortest-path diameter strictly below 4n/k.
- Shortest-path diameter reduction: The k-shortcut graph satisfies SPDiam(G′, w′) < 4n/k, providing the section’s diameter-reduction guarantee.Shortcut edges can be computed using the auxiliary graph construction described in Observation 3.12.
4 Algorithms on General Networks
The paper solves weighted SSSP on general networks by reducing it to an overlay network, reducing its shortest-path diameter, and then solving the reduced instance. This yields a (1+o(1))-approximation in ˜O(n^1/2D^1/4 + D) time, while also providing a ˜O(n)-time APSP algorithm.
- APSP: ˜O(n)-time APSP achieves a (1+o(1))-approximation by applying the h-hop k-source shortest paths algorithm with h = k = n.The section identifies APSP as a special case of the h-hop k-source shortest paths problem.
- Overlay reduction: ˜O(α + n/α + D)-time construction embeds an overlay network whose SSSP distances suffice to recover (1+o(1))-approximate distances in the original graph.The overlay is formed from sampled landmarks and weighted virtual edges based on bounded-hop distances.
- Shortest-path diameter reduction: ˜O(αβ + D)-time shortcut construction preserves all overlay distances while reducing shortest-path diameter to ˜O(α/β).The shortcut network keeps the same vertex set and exactly preserves pairwise distances.
- Shortcut-overlay SSSP: ˜O(Dα/β + α) time suffices for (1+o(1))-approximate SSSP on the shortcut overlay.The running time uses a lightweight bounded-hop shortest-path procedure whose communication can be simulated on the original network.
- Final SSSP bound: Setting α = n^1/2/D^1/4 and β = D^1/2 gives a ˜O(n^1/2D^1/4 + D)-time (1+o(1))-approximation for SSSP.When β ≥ α, setting β = α yields ˜O(D), which occurs for D ≥ n^2/3.
5 Algorithms on Fully-Connected Networks
On fully connected networks, the paper reduces shortest-path diameter using shortcuts and then applies bounded-hop shortest-path computation. This gives exact SSSP in ˜O(√n) time and (2+o(1))-approximate APSP in the same time.
- Exact SSSP: ˜O(√n)-time exact SSSP is obtained on fully connected networks by first reducing shortest-path diameter below 4√n.The reduced weights preserve every pairwise distance, allowing Bellman-Ford simulation to terminate after the reduced diameter number of iterations.
- Exact SSSP: SPDiam(G,w′) < 4√n and distG,w(u,v) = distG,w′(u,v) for all node pairs after shortcut augmentation.The exact SSSP phase then simulates Bellman-Ford on the augmented weights.
- Approximate APSP: ˜O(√n)-time (2+o(1))-approximate APSP uses Θ(√n log n) random sources and bounded-hop shortest paths after the same diameter reduction.Each node obtains approximate distances from the random sources and combines them with local shortcut information.
- Approximate APSP: The APSP final phase computes d′′(u,v), claimed to be a (2+o(1))-approximation of every original distance.The proof considers whether the relevant landmark intervals overlap and otherwise uses a random source in a suitable landmark set.
6 Lower Bound for Approximating APSP (Proof of Observation 1.4)
The paper proves that approximating weighted APSP requires linear time up to logarithmic factors, even on networks of diameter two. The proof encodes an arbitrary bit vector in edge weights and decodes it from the algorithm’s distance outputs.
- Weighted APSP lower bound: Ω(n/log n) time is required by any poly(n)-approximation algorithm for weighted APSP, even when D(G) = 2.The lower bound follows because each node must receive enough information to determine its distances to all other nodes.
- Unweighted consequence: The same communication argument gives an Ω(n/(α(n) log n)) lower bound for α(n)-approximation on unweighted networks.The weighted edge of length 2α(n) is replaced by a path of that length.
- Communication reduction: Alice encodes each bit by setting an edge weight to 1 or 2α(n), creating distances from a corresponding node to Bob that differ by approximation-detectable thresholds.For xi = 1 the distance is 2; otherwise it is 2α(n) + 1.
7 Open Problems
The paper leaves several questions about tightening approximation-time trade-offs, obtaining exact or asymmetric shortest paths, and improving fully connected-network bounds. In particular, it identifies a gap between the general-network upper and lower bounds for near-exact SSSP.
- General networks: ˜O(n^1/2D^1/4) versus ˜Ω(n^1/2) remains an open gap for (1+ε)-approximate SSSP on general networks.The paper asks whether the upper bound can be improved or whether a diameter-dependent lower bound exists.
- Exact computation: The paper asks whether SSSP can be solved exactly in sublinear time and APSP exactly in linear time.It notes that exact shortest paths can be important for protocols that use edge weights to control traffic.
- Further generalizations: The paper also asks for faster SSSP with asymmetric edge weights and for ˜O(√n + D)-time directed s-t reachability.For asymmetric SSSP, the paper notes that its lightweight SSSP method gives a separate (1+ε)-approximation bound, but not via shortest-path diameter reduction.
- Fully connected networks: Fully connected networks remain open for improving the ˜O(n^1/2)-time SSSP bound while keeping approximation at most two, or proving a nontrivial ω(1) lower bound.This question was previously raised by Elkin.