PaperlayerView exact revision on arXiv

Source-linked AI summary

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

arXiv:1504.07056v5cs.DCcs.DS

TL;DR

Distributed weighted SSSP had randomized near-exact algorithms with a running-time gap and a faster algorithm with a large approximation ratio, while no non-trivial deterministic solution was available. This paper combines deterministic center selection and hop-set construction to obtain a near-exact algorithm whose running time matches the known lower bound up to subpolynomial factors.

  • Problem

    Earlier distributed weighted SSSP algorithms traded a large approximation ratio for near-optimal time or near-exact approximation for extra time, and both were randomized.

    Source: §1 · p. 2

  • Method

    The algorithm deterministically selects centers to almost hit long paths and constructs a sparse hop set using bounded-distance clusters.

    Source: §1.2.2 · p. 5, §6 · p. 36

  • Results

    A deterministic (1+o(1))-approximation runs in (n^1/2+o(1) + D^1+o(1)) time, matching the known lower bound up to an n^o(1) factor.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The algorithm nearly settles the approximate SSSP running time while providing a deterministic solution for distributed weighted networks.

    Source: §1.1 · p. 3, §6 · p. 36

    The deterministic replacement for path hitting works only on undirected input graphs.

    Source: §6 · p. 36

Abstract

from arXiv · show

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here $n$ is the number of nodes in the network and $D$ is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized $(1+o(1))$-approximation $\tilde O(n^{1/2}D^{1/4}+D)$-time algorithm of Nanongkai [STOC 2014] by a factor of as large as $n^{1/8}$, and (ii) the $O(\epsilon^{-1}\log \epsilon^{-1})$-approximation factor of Lenzen and Patt-Shamir's $\tilde O(n^{1/2+\epsilon}+D)$-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of $\Omega(n^{1/2}/\log n + D)$ [Elkin STOC 2004] up to subpolynomial factors, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a $(2+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [OPODIS 2015]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an $(n^{o(1)}, o(1))$-hop set of size $n^{1+o(1)}$. We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g., ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen and Peleg PODC 2013], and partial distance estimation [Lenzen and Patt-Shamir PODC 2015].

1 Introduction

The paper asks whether deterministic approximation can make weighted single-source shortest paths faster than exact Bellman–Ford while approaching known distributed time bounds. It presents a near-lower-bound-time algorithm and deterministic techniques for selecting centers and constructing hop sets.

1 Introduction

  • The motivating gap was that earlier algorithms traded near-optimal running time for a large approximation ratio, or near-exact approximation for extra time, and both were randomized.Source: §1 · p. 2

1.1 Our Results

  • A deterministic (1+o(1))-approximation runs in (n^1/2+o(1) + D^1+o(1)) time, matching Elkin’s lower bound up to an n^o(1) factor.Source: §1.1 · p. 3
  • The same running time gives a (2 + o(1))-approximation of weighted diameter, whose ratio cannot be significantly improved without increasing running time.Source: §1.1 · p. 3
  • For the congested clique, the paper gives a deterministic (1 + o(1))-approximation in n^o(1) time and also approximates weighted diameter within that time.Source: §1.1 · p. 3
  • For arbitrary-order streaming, the algorithm solves (1 + o(1))-approximate SSSP in n^o(1) passes and n^1+o(1) space.Source: §1.1 · p. 3

1.2.1 Deterministic Path Hitting

  • The deterministic center-selection process assigns nodes to O(log n) types so every sufficiently long path is almost hit by a nearby center.Source: §1.2.1 · p. 4

1.2.2 Deterministic Hop Set Construction

  • A deterministic hop set of size n^1+o(1) reduces distances to paths with n^o(1) hops, using bounded-distance clusters that can be treated as a black box.Source: §1.2.2 · p. 5

1.3 Recent Developments

  • Later work eliminated the n^o(1) term in these bounds, and Elkin and Neiman gave sparse hop sets with a constant number of hops.Source: §1.3 · pp. 5–6

2 Preliminaries

The preliminaries define the weighted-graph and CONGEST model, formulate approximate SSSP, and review tools used by the algorithm, including weight rounding, source detection, and ruling sets.

2.1 Notation

  • The paper distinguishes hop diameter D from weighted diameter WD, defining distance as shortest-path weight and h-hop distance using paths with at most h edges.Graphs are weighted and undirected, with positive integer edge weights; the paper usually assumes weights are polynomially bounded.Source: §2.1 · pp. 6–7

2.2 CONGEST Model and Problem Formulation

  • In broadcast CONGEST, nodes communicate in synchronous rounds using O(log n)-bit messages, with each node sending the same message to all neighbors.The network is a weighted undirected graph, and each node initially knows its neighbors and incident edge weights.Source: §2.2 · p. 7
  • SSSP asks each node to learn its distance from source s; an α-approximation returns an estimate between the true distance and α times that distance.Approximate paths can be recovered by choosing a neighbor whose estimated distance plus edge weight does not exceed the node's estimate.Source: §2.2 · p. 8

2.3 Toolkit

  • Weight rounding scales edge weights to support efficient approximate shortest paths subject to a fixed hop limit.The paper reviews this as a repeatedly used toolkit technique.Source: §2.3 · p. 8
  • Source detection computes each node’s list of up to σ nearest sources within distance γ, ordered by distance and source ID.In weighted broadcast CONGEST, the cited deterministic algorithm runs in min(γ, WD) + min(σ, |S|) rounds.Source: §2.3 · pp. 8–9
  • A ruling set selects mutually separated nodes while keeping every other node in the target set within a bounded distance of a selected node.The paper cites a deterministic broadcast CONGEST construction taking O(c log n) rounds for a (c, cλ)-ruling set.Source: §2.3 · p. 10

3 Deterministic Hop Set Construction

This section develops deterministic hop reduction, using deterministic clusters and distance-range weight scaling to reduce hop counts with bounded size and approximation error. It then iterates the reductions to construct a small hop set with low stretch.

3 Deterministic Hop Set Construction

  • The section outlines a progression from weight-based hop reduction to hop-based reduction and then a hop set through repeated applications.The initial reduction uses additive error; repeated applications with edge-weight modifications are described as removing that additive error.Source: §3 · p. 10

3.1 Deterministic Clusters

  • Restricted clusters limit cluster computation to a distance range because straightforward computation is too inefficient for the paper’s noncentralized models.For each node, the procedure searches paths until nodes are no closer than nodes of higher priority.Source: §3.1 · pp. 10–11, §3.1.2 · p. 13

3.1.1 Computing Priorities A

  • A deterministic greedy hitting-set procedure builds node priorities using proximity lists of ˜O(n^(1/p)) nodes, targeting total cluster size O(pn^(1+1/p)).The lists come from weighted source detection; each next priority set approximately hits the lists, with a (1+ln n)-approximation to minimum size.Source: §3.1.1 · pp. 11–12

3.1.2 Computing Clusters

  • Procedure 2 computes restricted clusters and node-to-cluster distances, with total cluster size ˜O(pn^(1+1/p)).Source: §3.1.2 · pp. 13–14

3.2 Hop Reduction with Additive Error

  • A set F of size ˜O(pn^(1+1/p)) yields paths with at most (p+1)⌈d(u,v,G)/∆⌉ edges and weight at most (1+ϵ)d(u,v,G)+ϵn^(1/p)∆/(p+2).Here p=⌊log n/log(9/ϵ)⌋; the paths are in H=G∪F.Source: §3.2 · pp. 14, 16
  • The additive-error reduction extends a path by concatenating it with an inductively obtained y-to-v path of weight at most (1 + ε)d(y,v,G) + β.The inductive path has at most (p + 1)⌈d(y,v,G)/∆⌉ hops.Source: §3.2 · p. 19

3.3 Hop Reduction without Additive Error

  • For positive integer edge weights in {1,...,W}, with Δ≥1, h≥1, and 0<ε≤1, Procedure 4 computes an edge set F of size Õ(p n^{1+1/p} log W).It scales edge weights for each distance range 2^j to 2^{j+1}, applies Procedure 3, then scales the added edges back and returns their union.Source: §3.3 · p. 20

3.4 Computing the Hop Set

  • Repeated applications with ∆ = (p + 2)n^1/p reduce hop counts by a factor of 1/∆ per round, ultimately to n^1/p.The section notes that large ∆ is ineffective for paths already below ∆ hops and makes cluster computation too costly.Source: §3.4 · p. 22
  • The construction yields an (n^1/p, ε)-hop set F satisfying d_n^1/p(u,v,G ∪ F) ≤ (1 + ε)d(u,v,G) for every node pair.F is formed by combining the edge sets from repeated hop-reduction rounds.Source: §3.4 · pp. 22–23
  • For 1/ε ≤ polylog n, the construction produces an (n^o(1), o(1))-hop set of size O(n^1+o(1) log W).It performs ˜O(log W) cluster computations with p = Θ(log n/log log n) priorities up to distance O(n^o(1)), on graphs of size O(m^1+o(1) log W).Source: §3.4 · p. 23

4 Distributed Approximate Single-Source Shortest Paths Algorithm on Networks with Arbitrary Topology

The algorithm has two parts: deterministically construct an overlay network, then solve SSSP more efficiently on that overlay using previously developed procedures. It then combines these parts to finish the computation.

4 Distributed Approximate Single-Source Shortest Paths Algorithm on Networks with Arbitrary Topology

  • A deterministic overlay-network construction replaces the randomized construction used in Nanongkai.Solving SSSP on the resulting overlay suffices to solve the problem on the full network.Source: §4 · p. 23
  • The second part computes SSSP on the overlay using Procedures 1–5.The paper presents this as the more efficient overlay computation.Source: §4 · p. 23
  • The algorithm finishes by combining the overlay construction and overlay SSSP computation following Nanongkai.Figure 2 illustrates the overall approach.Source: §4 · p. 23

4.1 Computing an Overlay Network Deterministically

The section constructs a small deterministic overlay whose approximate SSSP solution can be converted into an approximate solution on the original graph. It does so by selecting centers that nearly hit long paths and estimating distances to those centers.

4.1 Computing an Overlay Network Deterministically

  • Under λ = O(log n) and W = poly(n), the overlay has size ˜O(√n/ϵ) and can be built in ˜O(√n/ϵ + D) time; center distances yield a (1 + ϵ)-approximation on G.The construction is modular: any method giving (1 + ϵ/3)-approximate distances from the source to all centers can be used.Source: §4.1 · p. 24

4.1.1 Types of Nodes

  • Every path of √n edges contains a node whose type is small relative to the path weight, enabling deterministic center selection without requiring a center on the path.The type is the smallest index j whose corresponding ball contains at least h nodes; Lemma 4.2 bounds 2^t(u) by 2ϵ̂ times the path weight.Source: §4.1.1 · p. 26

4.1.2 Selecting Centers via Ruling Sets

  • Ruling sets select a small set of centers: |V′| = O(√nλ log(nW)/ϵ), with a nearby center for a node on every √n-edge path.The nearby-center guarantee bounds the h*-hop distance by ϵ̃ times the path weight.Source: §4.1.2 · p. 27

4.1.3 Computing Distances to Centers

  • Partial distance estimation computes (1 + ϵ̃)-approximations of truncated distances from every node to every center.The procedure evaluates source detection on rounded-weight graphs and combines the resulting bounded-range distances into each estimate.Source: §4.1.3 · p. 28

4.1.4 Completing the Proof of Theorem 4.1

  • Combining source-to-center distances in the overlay with stored node-to-center estimates lets each node infer a (1 + ϵ)-approximation of its source distance.After receiving approximate overlay distances to all centers, a node computes the minimum sum of an overlay distance and its stored estimate, without further communication.Source: §4.1 · p. 24, §4.1.4 · pp. 28, 30

4.2 Computing a Hop Set on an Overlay Network

The algorithm builds a deterministic hop set on an overlay network by computing bounded-distance trees, priorities, clusters, and successive hop reductions. The resulting hop set is globally known and supports path reporting.

4.2.1 Computing Bounded-Distance Single-Source Shortest Paths

  • Bounded-distance shortest-path trees are computed in R + 1 breadth-first iterations, taking O(N + RD) rounds for distance R.Centers at level L broadcast tentative distances and parents; the original network diameter D determines communication cost.Source: §4.2.1 · p. 30

4.2.2 Computing Priorities

  • Priorities are built through repeated source detection and a deterministic greedy hitting-set approximation, taking n^1/2+o(1) + D^n^o(1) rounds.The construction repeats for p ≤ log n priorities, using R = N^o(1) and q = N^o(1).Source: §4.2.2 · p. 31

4.2.3 Computing Clusters

  • The cluster computation gives every center the clusters and distances for all centers, with total cluster size n^1+o(1), in n^1/2+o(1) + D^n^o(1) rounds.The message count is bounded by ~O(pN^1/p) = n^1/2+o(1).Source: §4.2.3 · pp. 31–32

4.2.4 Computing the Hop Reduction with Additive Error

  • Computing the hop reduction with additive error takes n^1/2+o(1) + D^n^o(1) rounds because cluster computation is its only communication-intensive step.The procedure computes the set F from cluster information without additional communication.Source: §4.2.4 · p. 32

4.2.5 Computing the Hop Reduction without Additive Error

  • The hop reduction without additive error takes n^1/2+o(1) log W + D^n^o(1) log W rounds, by running the additive-error procedure O(log(nW)) times.Edge-weight scaling and the final construction of F require no additional communication.Source: §4.2.5 · p. 32

4.2.6 Computing the Hop Set

  • An (n^o(1), o(1))-hop set is computed deterministically in n^1/2+o(1) log W + D^n^o(1) log W rounds on an overlay with n~O(√n) centers.Every center knows every edge in the hop set when the algorithm finishes.Source: §4.2.6 · p. 32

4.2.7 Routing via the Hop Set

  • The construction is path-reporting: each hop-set edge corresponds to a path of equal length in the overlay, whose nodes know their distances to both endpoints and their neighbors on the path.Global knowledge of clusters, partial shortest-path trees, and hop-set edges gives nodes the corresponding overlay paths.Source: §4.2.7 · p. 33

4.3 Final Steps

The final step turns approximate distances to centers into approximate SSSP distances across the network. It achieves a deterministic (1+o(1))-approximation in n^1/2+o(1) + D^1+o(1) rounds.

4.3 Final Steps

  • Approximating each center’s distance in G′ reduces to approximating its h-hop distance in H = G′ ∪ F, where F is the constructed hop set and h = n^o(1).The cited reduction uses a (n^o(1), o(1))-hop set.Source: §4.3 · p. 33
  • For each rounded-weight graph, the method computes an s-rooted shortest-path tree to distance R = O(h/ϵ), then takes the minimum scaled distance across the rounded graphs.The resulting value is used as a (1+o(1))-approximation of the h-hop distance, with correctness attributed to Lemma 2.3.Source: §4.3 · p. 33
  • n^1/2+o(1) + D^1+o(1) rounds suffice for deterministic (1+o(1))-approximate SSSP on weighted undirected networks with polynomially bounded positive integer weights.The algorithm broadcasts approximate source distances to all centers, then applies Theorem 4.1 to obtain the network-wide solution.Source: §4.3 · p. 33

5 Algorithms in Other Settings

The paper adapts its deterministic approximate SSSP approach to the congested clique and multipass streaming models. The adaptations retain subpolynomial-round or pass complexity, with n^1+o(1) space for streaming.

5.1 Congested Clique

  • Broadcasting M′ messages takes O(M′/n) rounds in the congested clique, reducing the hop-set construction to n^o(1) rounds.The reduction uses the clique routing scheme and the stated bound O(∑v∈V |C(v,A,R,G)|/n + R) = Õ(pn^1/p + R) = n^o(1).Source: §5.1 · p. 34
  • n^o(1) rounds suffice for deterministic (1+o(1))-approximate SSSP in the congested clique on weighted undirected networks with polynomially bounded positive integer weights.The algorithm computes a hop set, then uses h rounds of distributed Bellman–Ford to obtain h-hop distances.Source: §5.1 · p. 34

5.2 Streaming Algorithm

  • The streaming source-detection algorithm uses min(γ,WD) + min(σ,|S|) passes and O(n · (min(γ,WD) + min(σ,|S|))) space.For the priority computation, this yields n^o(1) passes and n^1+o(1) space.Source: §5.2 · p. 35
  • The streaming algorithm constructs clusters using n shortest-path trees in parallel, with total tree size bounded by Õ(pn^1+1/p) = n^1+o(1).The hop set is computed across Õ(log W) cluster computations; approximate SSSP then uses a streaming Bellman–Ford pass per iteration.Source: §5.2 · p. 35
  • n^o(1) passes and n^1+o(1) space suffice for deterministic (1+o(1))-approximate SSSP in the multipass streaming model.The stated guarantee applies to weighted undirected graphs with polynomially bounded positive integer weights.Source: §5.2 · p. 36

6 Conclusion and Open Problems

The paper presents deterministic approximate SSSP algorithms whose efficiencies match known lower bounds up to n^o(1), supported by a deterministic hop-set construction and a replacement for randomized hitting-set arguments. It also identifies open problems for directed graphs and exact SSSP.

6 Conclusion and Open Problems

  • The deterministic algorithms match known lower bounds up to an n^o(1) factor, using a deterministic hop-set construction and a process replacing randomized hitting-set arguments.The authors identify both techniques as important tools that may be useful beyond the presented algorithms.Source: §6 · p. 36
  • A (1+ϵ)-approximation with an ϵ^-O(1) polylog n overhead over known lower bounds was later shown in all the considered models.The authors also report that a lower bound ruled out the proposed (polylog n, o(1))-hop set of size Õ(n).Source: §6 · p. 36
  • The deterministic replacement for the hitting-set argument works only on undirected input graphs, leaving deterministic sublinear-time algorithms for directed SSSP and reachability open.The cited directed-graph results are randomized.Source: §6 · p. 36
  • Exact SSSP still has a gap between its best stated running time, O((n log n)^2/3 D^1/3 + (n log n)^5/6), and the Õ(√n + D) lower bound.The paper frames improving either the upper or lower bound as a natural open question.Source: §6 · p. 36

A Proof of Lemma 2.3

The proof compares shortest-path weights and distances in G and G_i, then uses hop-distance assumptions to derive claims (2), (4), and (3).

A Proof of Lemma 2.3

  • A shortest path in G_i, evaluated in G, has weight at least the distance between its endpoints in G.This establishes the comparison used to prove (2).Source: A Proof of Lemma 2.3 · pp. 36–37
  • A shortest h-hop path in G has weight in G_i at least the G_i distance, with the assumption d_h(u,v,G) ≥ 2^i used to prove (4).The passage gives the comparison and assumption but not the resulting inequality.Source: A Proof of Lemma 2.3 · p. 37
  • Claim (3) follows by combining (4) with the assumption d_h(u,v,G) ≤ 2^(i+1).The passage states this proof step without displaying the resulting inequality.Source: A Proof of Lemma 2.3 · p. 37

B Proof of Lemma 3.3

The proof uses probabilistic sampling to establish that a small hitting set exists for the family of sets C.

B Proof of Lemma 3.3

  • Sampling each element of U independently with probability 1/(2x) gives expected set size |U|/(2x), and the probability of exceeding |U|/x is at most 1/2.The bound follows from Markov’s inequality.Source: B Proof of Lemma 3.3 · p. 37
  • The union-bound estimate for the oversized-set event and empty-intersection events is 1/2 + k·1/(3k) = 1/2 + 1/3 < 1.The text identifies failure when at least one event E_j occurs; the displayed estimate bounds the combined events.Source: B Proof of Lemma 3.3 · p. 37
  • Because the total failure probability is below one, a hitting set T for C exists with |T| ≤ |U|/x.The proof concludes existence from the nonzero probability of sampling such a set.Source: B Proof of Lemma 3.3 · p. 37

C Ruling Set Algorithm

The algorithm iteratively filters nodes using ID bits and beep messages, producing a separated set that covers the nodes within a bounded distance.

C Ruling Set Algorithm

  • The algorithm runs for λ ID-bit iterations, using beep messages to filter nodes according to their ID bits.A node with bit 0 beeps within distance c−1; a node with bit 1 remains only if it hears no beep.Source: C Ruling Set Algorithm · p. 38
  • The output set T has pairwise node distances of at least c.For any pair closer than c, an iteration with differing ID bits removes one of the pair.Source: C Ruling Set Algorithm · p. 38
  • The algorithm takes O(c log n) rounds, and every node is within distance cλ of some node in T.Here λ is the length of the binary ID representation.Source: C Ruling Set Algorithm · p. 38
Loading 1504.07056v5…