Source-linked AI summary
Parallel Graph Decompositions Using Random Shifts
Gary L. Miller, Richard Peng, Shen Chen Xu
TL;DR
The paper addresses parallel decomposition of undirected unweighted graphs into small-diameter pieces separated by few edges, a subroutine used in several graph algorithms. It combines random shifts and shortest-path assignment in a simpler routine, achieving the same asymptotic guarantees as the best sequential algorithm. The resulting method provides O(log n/β) depth and O(m) work, while weighted-graph parallel performance remains unclear.
Problem
Parallel low-diameter decompositions are needed by graph algorithms, but strong-diameter requirements create sequential dependencies that complicate parallelization.
Method
The algorithm combines random shifts with one shortest-path invocation to assign vertices to low-diameter pieces.
Results
The algorithm produces a (β, O(log n/β)) decomposition with O(log^4 n/β) depth and O(m) work.
Takeaways & Limitations
The routine can replace the earlier Partition subroutine in parallel SDD solvers and supports the ball-growing view underlying low-stretch spanning-tree algorithms.
Takeaways & Limitations
The algorithm is developed for undirected unweighted graphs, and its parallel performance on weighted graphs is unclear.
Abstract
from arXiv · showhide
We show an improved parallel algorithm for decomposing an undirected unweighted graph into small diameter pieces with a small fraction of the edges in between. These decompositions form critical subroutines in a number of graph algorithms. Our algorithm builds upon the shifted shortest path approach introduced in [Blelloch, Gupta, Koutis, Miller, Peng, Tangwongsan, SPAA 2011]. By combining various stages of the previous algorithm, we obtain a significantly simpler algorithm with the same asymptotic guarantees as the best sequential algorithm.
1 Introduction
Low-diameter decompositions partition graphs into pieces with bounded strong diameter and few inter-piece edges, but strong-diameter parallelization faces sequential dependencies. The paper presents a randomized-shift algorithm achieving the desired decomposition with O(log n/β) depth and O(m) work.
- 1 Introduction: These decompositions support algorithms for sparsest cut, spanners, shortest paths, tree embeddings, and parallel SDD linear-system solvers.
- 1 Introduction: Low-diameter decompositions partition vertices into pieces with bounded strong diameter and at most a β fraction of edges crossing between pieces.Strong diameter requires paths between vertices of a piece to remain inside that piece.
- 1 Introduction: Strong-diameter parallelization is difficult because the next ball cannot begin until the previous piece is completed, creating dependencies as long as Ω(n).
- 1 Introduction: The algorithm combines parallel ball-growing and randomly shifted shortest paths into one routine that assigns vertices using a single shortest-path invocation.
- 1 Introduction: Theorem 1.2 gives a (β, O(log n/β)) decomposition with O(log^4 n/β) depth and O(m) work in the PRAM model.
2 Overview and Related Works
The overview interprets the method as parallel ball growing with independently sampled random delays, implemented through a parallel BFS that records each vertex’s originating shortest path. This design avoids sequential cluster formation and reduces the work to O(m), while weighted-graph parallel performance remains unclear.
- 2 Overview and Related Works: The routine samples each vertex’s exponential delay, computes the maximum shifted value, performs a parallel BFS, and assigns vertices to the shortest-path origin that reaches them.
- 2 Overview and Related Works: The method can be substituted into prior decomposition-based algorithms, including low-stretch spanning-tree and minor-free-graph separator constructions.
- 2 Overview and Related Works: Independent random radii make cluster formation identical across vertices, removing the sequential dependencies of sequential ball growing.
- 2 Overview and Related Works: Broadcasting only along shortest paths avoids the quadratic work that broadcasting to all vertices can incur on small-diameter graphs, yielding O(m) work.
- 2 Overview and Related Works: Weighted-graph adaptations have comparable sequential guarantees, but their parallel performance is left as an open question.
3 Background and Notations
The paper reviews shifted shortest-path decompositions, exponential order statistics, and the work–parallelism tradeoff caused by varying numbers of clusters. Its approach streamlines earlier components by using exponentially distributed shifts.
- 3 Background and Notations: For each piece, a designated center and distances from that center provide the notation used to estimate its diameter in an undirected graph.
- 3 Background and Notations: Earlier parallel decompositions balance many possible pieces against quadratic work on graphs where one piece may cover the entire graph.
- 3 Background and Notations: The prior shifted-shortest-path method obtains a (β, O(log^c n/β)) decomposition by sampling shifts uniformly from a sufficiently large range.
- 3 Background and Notations: The new scheme combines earlier components by replacing locally uniform shifts with exponential distributions whose density reflects the desired decrease in centers.
- 3 Background and Notations: Exponential variables are memoryless, and their successive order-statistic differences are independent exponential variables with rate depending on the remaining sample count.
4 Analysis
The analysis shows that exponentially shifted shortest paths produce a decomposition with bounded strong diameter and few edges crossing between pieces. The bounds follow from concentration of the maximum shift and a probability estimate for near-ties among shifted distances.
- Partition analysis: The partition assigns each vertex to the center minimizing shifted distance, yielding a (β, O(log n/β)) decomposition with high probability.The algorithm samples independent exponential shifts and breaks ties lexicographically.
- Strong diameter: A shortest path from a center to an assigned vertex remains inside that piece, so bounding center-to-vertex distance bounds strong diameter.The maximum shift is used as an upper bound on these distances.
- Strong diameter: With high probability, every shift is O(log n/β), while the expected maximum shift is H_n/β.The concentration bound is obtained from the exponential distribution and a union bound over vertices.
- Crossing edges: An edge can cross between pieces only when two shifted distances to its midpoint are within 1 of the minimum.This reduces the crossing-edge analysis to a near-tie event among shifted distances.
- Crossing edges: The near-tie lemma implies that each edge crosses pieces with probability O(β), giving an expected O(βm) crossing edges.The argument applies the lemma with c = 1 and uses linearity of expectation.
5 Implementation and Parallelization
The implementation replaces shifted shortest paths with a BFS-based procedure using integer distances, delayed source edges, and tie-breaking. Parallel BFS yields the stated depth and work bounds, while the decomposition can be verified efficiently.
- BFS implementation: Shifted shortest paths are simulated with a super source, while fractional shift parts act as tie-breakers for equal integer distances.Non-unit source edges are handled by adding unvisited vertices when the BFS frontier reaches their lengths.
- Parallelization: The BFS implementation computes the decomposition in O(log n/β) depth and O(m) work under the stated parallel BFS bound.The maximum explored distance is bounded by O(log n/β).
- Verification: The resulting decomposition can be verified in O(log n) depth and O(m) time.
- Practical implementation: Random permutations may replace explicit exponential shifts in practice, but the resulting distributional changes require further analysis or empirical study.
6 Conclusion / Remarks
The paper presents a simple parallel low-diameter decomposition algorithm for undirected unweighted graphs, with O(m) work and polylogarithmic depth. It can replace a decomposition routine in SDD linear-system solvers and may improve other ball-growing applications, while weighted extensions remain challenging.
- 6 Conclusion / Remarks: The algorithm computes low-diameter decompositions with O(m) work and polylogarithmic depth for undirected unweighted graphs.The supplied result states the depth as O(log n/β).
- 6 Conclusion / Remarks: Replacing Partition from with this routine yields a faster algorithm for solving SDD linear systems.
- 6 Conclusion / Remarks: The approach offers a different view of ball growing, which underlies the best sequential low-stretch spanning-tree algorithms.
- 6 Conclusion / Remarks: Extending the analysis to weighted graphs is straightforward, but controlling depth is harder because hop count no longer closely tracks diameter.
A Alternate Proof of Key Partition Lemma
The alternate proof abstracts shifted-distance competition into independent exponential shifts and bounds the chance that another shifted value nearly ties the minimum. It integrates event probabilities using exponential densities and cumulative distribution functions, then obtains an O(βc) bound.
- A Alternate Proof of Key Partition Lemma: Linearity of expectation converts the indicators E_i into a bound on the expected number of indices whose shifted values lie within c of the minimum.
- A Alternate Proof of Key Partition Lemma: For a fixed shifted value t = d_i−δ_i, the near-minimum event occurs when every other shift satisfies δ_j ≤ d_j−t+c.Independence allows the corresponding exponential cumulative distribution functions to be multiplied.
- A Alternate Proof of Key Partition Lemma: The integral is truncated at t = d_1+c because beyond that point the minimum candidate’s exponential density and cumulative distribution terms vanish.
- A Alternate Proof of Key Partition Lemma: Independent exponential shifts make the probability that the smallest and second-smallest shifted values differ by at most c equal to O(βc).The proof first bounds the expected number of near-minimizing indices by exp(βc), then applies Markov’s inequality for c = 1.