Source-linked AI summary
Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
Guy Blelloch, Jeremy Fineman, Julian Shun
TL;DR
The paper asks whether greedy MIS and maximal matching can retain the sequential algorithm’s deterministic result while gaining parallelism. It parallelizes dependency-respecting greedy iterations under random orderings and obtains polylogarithmic depth with linear-work variants. Experiments show strong speedups and a smooth work–parallelism tradeoff, while the dependence-length bound remains an open target for improvement.
Problem
Greedy parallel MIS and matching algorithms can be difficult to make faster than simple sequential greedy algorithms while preserving their results.
Method
The paper parallelizes greedy MIS and maximal matching by processing dependency-respecting iterations, including prefix-based variants that trade work for parallelism.
Results
Random vertex or edge orderings give polylogarithmic depth for greedy MIS and matching, while the algorithms preserve the sequential result and achieve reported speedups of 14–24x on 32 processors.
Takeaways & Limitations
Randomized orderings make simple sequential greedy algorithms practical to parallelize without changing their outputs, with prefix size providing a smooth work–parallelism tradeoff.
Takeaways & Limitations
The paper leaves open whether the dependence length can be improved from its stated polylogarithmic bound to O(log n).
Abstract
from arXiv · showhide
The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices in arbitrary order adding a vertex to the resulting set if and only if no previous neighboring vertex has been added. In this loop, as in many sequential loops, each iterate will only depend directly on a subset of the previous iterates (i.e. knowing that any one of a vertices neighbors is in the MIS or knowing that it has no previous neighbors is sufficient to decide its fate). This leads to a dependence structure among the iterates. If this structure is shallow then running the iterates in parallel while respecting the dependencies can lead to an efficient parallel implementation mimicking the sequential algorithm. In this paper, we show that for any graph, and for a random ordering of the vertices, the dependence depth of the sequential greedy MIS algorithm is polylogarithmic (O(log^2 n) with high probability). Our results extend previous results that show polylogarithmic bounds only for random graphs. We show similar results for a greedy maximal matching (MM). For both problems we describe simple linear work parallel algorithms based on the approach. The algorithms allow for a smooth tradeoff between more parallelism and reduced work, but always return the same result as the sequential greedy algorithms. We present experimental results that demonstrate efficiency and the tradeoff between work and parallelism.
1 Introduction
The paper shows that randomized vertex or edge orderings expose substantial parallelism in greedy MIS and maximal matching while preserving the sequential result. Prefix-based implementations provide a work–parallelism tradeoff, with experiments showing strong speedups and deterministic outputs.
- Randomized orderings give greedy MIS polylogarithmic depth on any graph, extending earlier analyses limited to random graphs.The result addresses the general-graph setting despite the P-completeness of lexicographically first MIS under arbitrary orderings.
- Prefix size controls the tradeoff between redundant work and parallelism, with size one recovering the sequential algorithm and larger prefixes exposing more parallelism.The paper describes prefix sizes that guarantee linear work.
- For a fixed ordering, any dependency-respecting schedule returns the same result as the sequential algorithm, providing deterministic parallel outputs.This allows algorithm choice to vary by platform without changing the computed MIS or matching result.
- The same approach applies to greedy maximal matching, yielding polylogarithmic depth for random edge orderings and preserving the sequential matching result.The direct MIS reduction through line graphs is asymptotically inefficient, so the matching algorithm is adapted to retain linear work.
- 14–24x speedup on 32 processors was achieved experimentally, while the prefix-based MIS implementation used only a modest processor count to outperform optimized sequential code.The experiments compare prefix-based MIS with sequential implementations and with an efficient implementation of Luby’s algorithm.
2 Notation and Preliminaries
The paper establishes notation for graph size, neighborhoods, induced subgraphs, MIS and matching, and analyzes algorithms in the CRCW PRAM work-depth model.
- The paper uses n and m for the numbers of vertices and edges, respectively, and defines neighborhood operators for vertices and edges.N(v) abbreviates the neighborhood of a single vertex.
- An MIS is characterized by having no internal neighboring vertices and covering every vertex through itself or a neighbor; a maximal matching is defined analogously over edges.The notation expresses these conditions using neighborhood unions and intersections.
- Algorithms are analyzed in the CRCW PRAM work-depth model, where work counts operations and depth counts parallel time steps.The analysis assumes arbitrary-write semantics.
3 Maximal independent set
The paper parallelizes greedy MIS by processing vertices whose earlier neighbors are resolved, while preserving the sequential algorithm’s result. Random vertex orderings yield polylogarithmic dependence depth even on arbitrary graphs, analyzed through prefix-based rounds and priority DAGs.
- Sequential and parallel algorithms: The sequential greedy algorithm processes the earliest remaining vertex, adds it to the MIS, and removes it together with its neighbors.The resulting set is the lexicographically first MIS for the ordering π.
- Sequential and parallel algorithms: The parallel algorithm adds vertices as soon as all earlier neighbors are classified, yet returns exactly the same MIS as the sequential algorithm.An induction over the vertex ordering establishes equivalence, although vertices may be accepted earlier in parallel.
- Prefix-based algorithm: Prefix processing trades parallelism for less redundant work, with prefix size one recovering the sequential algorithm.The modified algorithm processes only a δ-prefix each round, computes MIS on that prefix, and removes the prefix and neighbors of newly selected MIS vertices.
- Analysis: The analysis preserves uniform randomness among remaining vertices by using prefix-based rounds instead of directly analyzing the fully parallel algorithm.Each round reduces the maximum remaining degree geometrically with high probability, while priority-DAG paths within rounds remain logarithmic.
- Analysis: For arbitrary graphs, random ordering bounds consecutive-edge probabilities in priority-DAG paths despite dependencies among those events.The bound increases as positions are exposed because fewer vertices remain, which requires an analysis different from the independent-edge random-graph case.
- Dependence depth: O(log^2 n) iterations w.h.p. suffice for the parallel greedy MIS algorithm under a random vertex ordering.The theorem states an O(log Δ log n) dependence length, which is O(log^2 n) because Δ ≤ n.
4 Achieving a linear work MIS algorithm
The paper develops two linear-work implementations of parallel greedy MIS: one explicitly traverses the priority DAG, while the experimentally used approach processes suitably sized prefixes. Both preserve the sequential result while exploiting shallow dependence and sparse prefixes.
- 4 Achieving a linear work MIS algorithm: The priority-DAG implementation processes only roots and their neighbors, so every edge is processed once and total work is linear.A second prefix-based implementation is simpler and is used in the experiments.
- 4 Achieving a linear work MIS algorithm: O(m) total work and O(log n) depth per iteration follow from maintaining roots and using misCheck operations to generate the next root set.The implementation marks roots and neighbors, then checks neighbors’ neighbors; at most m checks are needed overall.
- 4 Achieving a linear work MIS algorithm: Increasing prefix size raises both work and parallelism, while a prefix of size 1 recovers the sequential O(m)-work algorithm with Ω(n) depth.Internal and external edges are treated differently: internal edges may be processed repeatedly, whereas external edges are processed once.
- 4 Achieving a linear work MIS algorithm: For δ < k/d, a random prefix has expected O(k|P|) internal edges and at most O(k|P|) vertices incident to internal edges.These sparsity bounds support repeated processing of small prefixes without exceeding linear expected work.
- 4 Achieving a linear work MIS algorithm: Algorithm 3 achieves O(log^4 n) depth and expected O(n + m) work on a CRCW PRAM, with the depth bound holding with high probability.The implementation groups rounds into superrounds, packs surviving induced subgraphs, and processes them using their dependence length.
5 Maximal Matching
For maximal matching, the paper parallelizes the greedy edge-order algorithm by processing edges with no higher-priority adjacent edge and maintaining roots through lazy deletion and local checks. The resulting implementation preserves the greedy matching and achieves linear work with polylogarithmic depth.
- 5 Maximal Matching: Algorithm 4 processes ready edges with no adjacent higher-priority edges, then deletes those edges and their neighbors.This is the edge-order analogue of the greedy MIS procedure.
- 5 Maximal Matching: A random edge ordering yields O(log^2 m) rounds with high probability, because the matching process corresponds step-for-step to greedy MIS on the line graph.The line-graph reduction establishes the round bound but can be asymptotically larger than the original graph.
- 5 Maximal Matching: Lazy deletion and sorted incident-edge arrays let mmCheck operations identify surviving highest-priority edges without scanning neighbors’ neighbors.Any l mmCheck operations require O(l + m) total work, with O(log m) depth per operation.
- 5 Maximal Matching: O(m) total work and O(log^3 m) depth with high probability are achieved for the parallel greedy maximal-matching algorithm.The implementation uses a random edge permutation and CRCW PRAM primitives.
6 Experiments
Experiments vary prefix size and compare prefix-based MIS and maximal-matching implementations with optimized sequential baselines, plus Luby’s algorithm for MIS. Larger prefixes increase work and parallelism, while carefully chosen prefixes deliver substantial speedups and outperform Luby’s implementation.
- 6 Experiments: The experiments use a sparse random graph with 10^7 vertices and 5 × 10^7 edges and an rMat graph with 2^24 vertices and 5 × 10^7 edges.Runs were performed on a 32-core processor with hyper-threading and 64GB of memory.
- 6 Experiments: Increasing prefix size increases both total work and parallelism for MIS and maximal matching.Sequential implementations have work and outer-loop rounds equal to the input size.
- 6 Experiments: 14–17x MIS speedup is achieved on 32 processors, and the prefix-based MIS implementation is 4–8 times faster than Luby’s algorithm.The prefix-based MIS implementation beats the serial version with more than 2 processors, whereas Luby’s requires at least 16.
7 Conclusion
For randomly ordered inputs, greedy MIS and MM have polylogarithmic depth, enabling practical parallel implementations with tunable work and parallelism.
- 7 Conclusion: The greedy MIS and MM algorithms have polylogarithmic depth when vertices or edges are randomly ordered.This yields random lexicographically first solutions for both problems.
- 7 Conclusion: Prefix size provides a smooth tradeoff between parallelism and total work, with smaller prefixes reducing redundant work.
- 7 Conclusion: The approach achieves strong speedups and outperforms serial counterparts using only a modest number of processors.
- 7 Conclusion: Whether the algorithms' dependence length can be improved to O(log n) remains an open question.