PaperlayerView exact revision on arXiv

Source-linked AI summary

More Efficient Parallel $(\Delta+1)$-Edge Coloring

Jeremy T. Fineman, Seyed Ali Mohammadi

arXiv:2609.35693v1cs.DS

TL;DR

The paper studies parallel (∆+1)-edge coloring and the color-reduction problem. It improves color reduction with deterministic and randomized algorithms; the randomized algorithm achieves O(m∆^2 log^2 n log ∆) work and O(∆^2 log^2 n log ∆) span with high probability.

  • Problem

    The task is to find a proper (∆+1)-edge coloring of a simple graph with maximum degree ∆, with color reduction also formalized as removing one color from a proper coloring.

    Source: §1 · pp. 1, 3

  • Method

    The paper improves the color-reduction step, using parallel Vizing operations on conflict-free subsets deterministically and sampled centers followed by conflict removal in the randomized algorithm.

    Source: §1 · p. 3, §3.4 · p. 19, §4.4 · p. 38

  • Results

    The randomized color-reduction algorithm achieves O(m∆^2 log^2 n log ∆) work and O(∆^2 log^2 n log ∆) span with high probability, and Corollary 3 transfers these bounds to (∆+1)-edge coloring.

    Source: Results · p. 3

  • Takeaways & Limitations

    Ignoring logarithmic factors, the randomized algorithm essentially reaches the fan-conflict bottleneck, coloring each uncolored edge with probability Ω(1/∆^2) per round.

    Source: §1 · p. 2

    Keeping path-fan conflict in-degree at O(∆) depends on color-disjointness; without it, the in-degree can rise to O(∆^2).

    Source: §3.2 · p. 15

Abstract

from arXiv · show

This paper gives two parallel algorithms for $\Delta+1$ edge coloring, where $\Delta$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(\Delta^3)$ span and $\tilde{O}(m \Delta^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}(\Delta^2)$ span and $\tilde{O}(m \Delta^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(\Delta^4)$ span and $\tilde{O}(m \Delta^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(\Delta)$ improvement on span and $\tilde{O}(\Delta^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(\Delta^2)$ and $\tilde{O}(\Delta^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.

1 Introduction

The paper targets efficient parallel (∆+1)-edge coloring, where fan and alternating-path recolorings can interfere. It improves color reduction and uses deterministic and randomized strategies to process more edges in parallel, with the randomized algorithm approaching the stated fan-conflict bottleneck.

1 Introduction

  • The parallel challenge is to color many uncolored edges simultaneously despite interference among fan rotations and alternating-path recolorings.A fan may intersect fans from Θ(∆2) other uncolored edges, yielding a stated Ω(∆2) round, span, and work bottleneck.Source: §1 · p. 2

Results

  • The randomized (∆+1)-edge-coloring algorithm achieves ˜O(∆2) span and ˜O(m∆2) work with high probability, approaching the stated fan-conflict bottleneck.Theorem 2 gives color-reduction bounds of O(∆2 log2 n log ∆) span and work O(m∆2 log2 n log ∆), both with high probability.Source: §1 · p. 2, Results · p. 3

1 Introduction

  • Color reduction starts from a palette slightly larger than ∆+1 and repeatedly removes one color, with the reduction subroutine incorporated into divide-and-conquer.The reduction step uncolors a least-used color class, a matching of size O(m/∆), then recolors those edges.Source: §1 · pp. 2–3

Results

  • The deterministic color-reduction algorithm has O(m∆3 log2 n) work and O(∆3 log4 n) span.The corresponding (∆+1)-edge-coloring algorithm inherits these bounds.Source: Results · p. 3

Overview of the Algorithms

  • The deterministic algorithm processes Θ(∆) color-disjoint color pairs at once, improving total work by a Θ(∆2) factor over Elkin and Khuzman’s approach.It selects a color-pair class, builds a conflict graph, and colors the edges in a large independent set.Source: Overview of the Algorithms · p. 4

Random matching of the palette.

  • Random activation and sampling reduce each uncolored edge’s relevant conflicts to O(∆) with constant probability, so each edge is colored with probability Ω(1/∆2) per round.The algorithm then colors all edges in O(∆2 log n) rounds with high probability.Source: Random matching of the palette · pp. 5–6

Related Work

  • Earlier parallel (∆+1)-edge-coloring algorithms had higher ∆-dependent and logarithmic runtime factors than the paper’s deterministic and randomized algorithms.Elkin and Khuzman’s smallest-span general-graph algorithm used O(m∆5 log4 n) work and O(∆4 log4 n) span.Source: Related Work · p. 6

Roadmap

  • The paper presents preliminaries, then deterministic processing of color-disjoint pairs, followed by randomized procedures including missing-color randomization.Additional technical details and proofs are deferred to Appendix A.Source: Roadmap · p. 7

2 Preliminaries

The preliminaries define the partial-coloring framework and explain how Vizing fans and alternating paths turn an uncolored edge into a colorable one. They also specify the parallel model and supporting routines used by the algorithms.

  • A partial coloring leaves a matching of edges uncolored, and each vertex has a designated missing color chosen from its available colors.Source: §2 · p. 7
  • A fan rotation shifts missing colors along the fan and colors the original uncolored edge directly when the fan is trivial.Source: §2 · p. 7
  • For a nontrivial fan, flipping the maximal alternating path for its required color pair makes the fan or a prefix trivial, enabling rotation to color the edge.Source: §2 · pp. 8–9
  • The algorithms use the arbitrary CRCW PRAM model and measure complexity by total work and longest dependency-chain span; standard sorting, prefix-sum, reduction, and compaction routines are assumed.Source: §2 · pp. 9–10
  • Component identification, fan construction, and rotation have stated parallel bounds, with rotations of pairwise vertex-disjoint trivial fans taking O(m) work and O(1) span.Source: §2 · p. 10
  • The preliminaries also provide a deterministic large-independent-set routine and a concentration inequality for analyzing the randomized algorithm.Source: §2 · pp. 10–11

3 Building Blocks and Deterministic Algorithm

This section develops parallel building blocks for managing conflicts and constructing a conflict graph, then uses conflict-free sets of Vizing operations in a deterministic algorithm to color edges.

3 Building Blocks and Deterministic Algorithm

  • The deterministic algorithm partitions color pairs into O(∆) color-disjoint sets, selects the largest set per round, and colors a large conflict-free subset of its u-edges in parallel.Source: §3 · p. 11

3.1 Processing Color-disjoint Pairs in Parallel

  • All nonempty bichromatic components for color-disjoint pairs can be identified in O(m log n) work and O(log n) span, then flipped simultaneously in O(m) work and O(1) span.The flips preserve a proper partial coloring, leave uncolored edges unchanged, and produce an outcome independent of flip order.Source: §3.1 · pp. 11, 13

3.2 Conflicts

  • Fan-fan conflicts number O(∆^2) per active fan, while a fan conflicts with paths of O(∆) other u-edges when required color pairs are color-disjoint.Source: §3.2 · pp. 14–15

3.3 Conflict Graph

  • The conflict graph Gconf(A) has O(∆²|A|) edges; if the underlying required pairs of its nontrivial edges belong to a color-disjoint set, conflicts are detected and the graph constructed in O(m log n + ∆²|A| log n) work and O(log n) span.Source: §3.3 · p. 16
  • Deduplicating conflict records yields one edge per conflicting active u-edge pair, and constructing Gconf(A) takes O(m log n + Δ^2|A| log n) work and O(log n) span.Source: §3.3 · p. 18

3.4 The Deterministic Algorithm

  • Partitioning color pairs into O(Δ) color-disjoint sets and selecting a largest active set enables each round to color an Ω(1/Δ^3) fraction of remaining edges, so O(Δ^3 log n) rounds suffice.Source: §3.4 · pp. 18, 19, 22
  • Given a partial (Δ + 1)-edge coloring whose uncolored edges form a matching of size O(m/Δ), Algorithm 1 colors them deterministically in O(mΔ^3 log^2 n) work and O(Δ^3 log^4 n) span.Source: §3.4 · p. 22

4 The Randomized Algorithm

The section develops randomized methods for constructing a proper (Δ+1)-edge coloring, using palette matching, activation, and conflict handling for trivial and nontrivial fans. It establishes high-probability work and span bounds for the randomized algorithm and also presents a deterministic algorithm.

4 The Randomized Algorithm

  • Each round produces a conflict-free set S whose centers can be colored simultaneously, coloring Ω(λ/Δ²) edges in expectation.The algorithm samples active centers, detects and orients conflicts, and removes sampled centers with an oriented conflict.Source: §4 · p. 25

4.1 Randomizing Missing Colors in Parallel

  • The randomized bounds apply even when the matching of uncolored edges contains O(m) edges, and restricting to Γ retains more than half the centers without changing asymptotic rounds, work, or span.The subpalette preprocessing costs O(m log n) work and O(log n) span.Source: §4.1 · pp. 25–26
  • Each missing-color bit phase flips color-disjoint bichromatic components in parallel, preserving a proper partial coloring and the set of uncolored edges.Each phase takes O(m log n) work and O(log n) span; the phases randomize each center’s designated color over Γ.Source: §4.1 · pp. 26–27
  • Every retained center’s final designated missing color is uniform over Γ; among any set of at most Δ² other centers, fewer than 2Δ match it in expectation.The same-color count is O(Δ + log n) with high probability; it is O(Δ) when Δ = Ω(log n).Source: §4.1 · pp. 28–30
  • For every fixed center u ∈ W and every a ≥ 1, Pr[Nu ≥ aΔ] < 2/a; in particular, Pr[Nu < 20Δ] > 9/10.Source: §4.1 · p. 30

4.2 Random Matching of the Palette

  • A uniformly random matching of the full palette activates each center with probability Θ(1/Δ), with O(Δ) conflicting active fans per active center with constant probability.Fans and their required pairs are built after missing colors are randomized; the full palette is needed because a required pair’s second color may lie outside Γ.Source: §4 · p. 25, §4.2 · pp. 30–31
  • Pr[πeu ∈ M and Du < 23Δ] ≥ 1/[5(Δ + 1)] for each fixed nontrivial center, giving an active center with fewer than 23Δ conflicting active fans.A nontrivial center is M-active with probability Θ(1/Δ); conditioned on activation, it has fewer than 23Δ conflicting active fans with probability at least 2/5.Source: §4.2 · pp. 32–34

4.3 Trivial Fans and Activated Conflicts

  • Trivial centers activate independently with probability 1/(2Δ); conditioned on activation, they have fewer than 5Δ active conflicting fans with probability at least 9/10.For nontrivial centers, the bound is fewer than 28Δ total active fan conflicts with probability at least 3/10; thus both fan types have O(Δ) conflicts with constant probability when active.Source: §4.3 · pp. 35–37

4.4 Random Sampling and Conflict Removal

  • A sampled center with Bu < c1Δ survives deterministic conflict removal with probability at least 1/2, and the surviving set is conflict-free.Each active center is sampled independently with probability 1/(2c1Δ); the deterministic step orients conflicts and removes centers with an incoming oriented conflict.Source: §4.4 · p. 38
  • Random sampling, required bichromatic-component identification, and conflict removal take O(m log n) expected work and O(log n) span.For a fixed sampled set S0, component identification and conflict removal take O(m log n + Δ^2|S0| log n) work and O(log n) span.Source: §4.4 · p. 39
  • S is conflict-free, and every fixed center belongs to it with probability Θ(1/Δ^2), allowing its Vizing operations to run in parallel.Conflict Removal deletes an endpoint of every fan-fan or path-fan conflict; its sampled-set-dependent work is O(m log n) in expectation and its span is O(log n).Source: §4.4 · p. 40

4.5 Complete Algorithm and its Analysis

  • Each round selects over half the centers for processing, randomizes their missing colors, activates and samples centers, removes conflicts, then performs parallel Vizing operations.For each fixed selected center, Theorem 45 supplies a constant-probability inclusion in the conflict-free set, driving round progress.Source: §4.5 · pp. 41–42
  • O(mΔ^2 log^2 n log Δ) work and O(Δ^2 log^2 n log Δ) span color a given matching of uncolored edges with high probability.Algorithm 2 assumes a proper partial (Δ+1)-edge coloring whose uncolored edges form a matching.Source: §4.5 · p. 41
  • O(Δ^2 log n) rounds suffice with high probability, since each round colors a conflict-free set of edges while preserving properness and leaving the remaining uncolored edges a matching.The algorithm’s correctness follows by applying the parallel Vizing operations to the surviving set in each round.Source: §4.5 · pp. 43, 46

4.6 Solving Problem 1

  • O(mΔ^2 log^2 n log Δ) work and O(Δ^2 log^2 n log Δ) span produce a proper (Δ+1)-edge coloring with high probability on ARBITRARY CRCW PRAM.The algorithm replaces each Reduce-Color call in Elkin and Khuzman’s framework with Algorithm 2, with modifications for uncoloring a color class and handling the palette.Source: §4.6 · pp. 46–47
  • With high probability, the randomized algorithm outputs a proper (Δ+1)-edge coloring using O(mΔ^2 log^2 n log Δ) work and O(Δ^2 log^2 n log Δ) span.Source: §4.6 · pp. 47–48
  • Fewer than n color-matching calls each fail with probability at most n^-(c+1), yielding simultaneous success probability at least 1−n^-c.Conditioned on all calls succeeding, the reduction framework produces a proper (Δ+1)-edge coloring.Source: §4.6 · pp. 47–48
  • The deterministic algorithm outputs a proper (Δ+1)-edge coloring with O(mΔ^3 log^2 n) work and O(Δ^3 log^4 n) span.Source: §4.6 · pp. 48–49

A Additional Details

The additional details explain how the algorithms maintain coloring data, build and apply fans, and bound randomized phase progress. They also establish the stated deterministic complexity and supporting component-identification costs.

Component identification

  • O(n log n) work and O(log n) span identify connected components and the endpoints of path components.The endpoint procedure uses initialization and two parallel write phases.Source: A Additional Details · p. 52

Data structure

  • Maintaining and updating coloring tables avoids repeating an O(mΔ)-work initialization in every round.The tables support constant-work missing-color tests, and endpoints of uncolored edges retain two distinct missing colors.Source: A Additional Details · pp. 52–53

Fan construction and rotation

  • All maximal fans can be constructed and classified in O(m log Δ) work and O(log Δ) span, even when they overlap.The construction writes each fan to its center’s array; trivial fans can then be rotated in O(m) work and O(1) span.Source: A Additional Details · pp. 53–54

Randomized analysis

  • With probability at least 1−1/poly(n), the surviving-center bound is D=O(Δ) when Δ=Ω(log n).More generally, the proof obtains D<16(Δ+λ) with probability at least 1−b e^−λ, then sets λ=c log n.Source: A Additional Details · pp. 57–58
Loading 2609.35693v1…