Tentative Vizing-Chain Nibbling for Massively Parallel Edge Coloring

Edge coloring means giving every edge of a graph a color so that no two edges sharing a vertex get the same color. Vizing's theorem guarantees that $\Delta+1$ colors always suffice, where $\Delta$ is the maximum degree. Sequential algorithms reach this bound by repairing conflicts along Vizing chains: paths whose edges alternate between two colors, and whose colors can be swapped to free up a color for an uncolored edge. In massively parallel computation (MPC), where a graph is spread over many machines that each hold far less memory than the number of vertices and talk to each other in synchronous rounds, the best known approach gives up on chains. It settles for $\Delta+\tilde O(\Delta^{3/4})$ colors in $O(1)$ rounds by partitioning vertices and palettes (Streaming and Massively Parallel Algorithms for Edge Coloring). Chains are avoided because following one edge at a time costs one communication round per step.

We propose to bring chains back into MPC by combining two existing ideas. The first is the nibble: a round-based scheme in which uncommitted items make tentative random choices, and any choice that collides with another is discarded and retried in a later round. The second is recursive stitching, also called pointer doubling: a path of length $L$ is traversed in $O(\log L)$ rounds by repeatedly joining segments whose lengths double each time. In our algorithm, every uncolored edge proposes a chain flip at once. Each proposer finds the far end of its two-colored chain by doubling. Proposals whose chains overlap are thrown away, nibble-style, and the rest are flipped together. The leftover edges are handled in later phases with geometrically fewer edges. The question we want to answer is whether the fraction of proposals that survive each round stays constant. If it does, $(\Delta+1)$- or $(\Delta+O(1))$-edge coloring is possible in MPC within a polylogarithmic number of rounds and with machine memory sublinear in $n$, closing much of the gap between the parallel color count and Vizing's bound.

Core Claim

The bottleneck in parallel Vizing-style coloring is not traversing a single chain. Once two color classes are fixed, their union has maximum degree 2, so locating a chain's endpoint is list ranking, and pointer doubling solves that in $O(\log L)$ rounds. We take this step from the walk-stitching literature essentially as-is and do not claim it as new. The open problem is concurrency: thousands of uncolored edges each want to flip a chain, and their chains overlap. Our claim is that nibble-style tentative proposals with conflict discarding, applied to chain flips rather than to color choices, keep a constant fraction of proposals alive per round. We expect this when proposers draw their pair of colors at random from popular missing colors, which is the randomization that keeps chains short in Vizing's Theorem in Near-Linear Time. If the claim holds, the total round count is roughly

$$R \approx O(\log m_0) \cdot O(\log \bar L),$$

where $m_0$ is the number of edges still uncolored after an initial nibble phase and $\bar L$ is the typical chain length at that point. The first factor follows from a constant survival fraction, which shrinks the uncolored set geometrically. The second is the cost of doubling.

Relation to Prior Work

The method draws on three bodies of work. The nibble papers supply the round structure and the analysis style: tentative choices, conflict discarding, and concentration of the remaining palettes. These are Near-Optimal, Distributed Edge Colouring via the Nibble Method, Online Edge Coloring Algorithms via the Nibble Method, and Nibbling at Long Cycles. All of them nibble over colors and stop at $(1+\epsilon)\Delta$. We nibble over chain flips in order to push toward $\Delta+1$.

Vizing's Theorem in Near-Linear Time supplies the chain machinery. It reaches $O(m\log\Delta)$ sequential time by popularizing missing colors, using separable collections of fans, and making randomized path flips. It remains a sequential algorithm, so it is our quality reference rather than a parallel competitor.

The walk-stitching papers supply the traversal primitive. Walking Randomly, Massively, and Efficiently generates length-$\ell$ random walks in $\Theta(\log \ell)$ MPC rounds. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs uses layered stitching for connectivity. Both of these exist to keep random walks free of correlation bias. Our chains are deterministic once the color pair is chosen, so that bias problem does not arise. Our problem is different: overlapping chains interfere with each other.

Two results limit what we can claim. The same connectivity paper proves an unconditional $\Omega(\log n)$-round lower bound for machines with polylogarithmic memory, and Walking Randomly, Massively, and Efficiently ties $\Theta(\log\ell)$ to the 1-vs-2-Cycles conjecture. Long two-colored cycles are exactly the hard instances, so we do not aim for $O(1)$ rounds. We aim for rounds polylogarithmic in $\Delta$ and doubly logarithmic in $n$ when chains are short, with $O(\log n)$ per phase as the fallback.

Research Program

Phase A. The algorithm first runs an MPC nibble for $O(\log(1/\epsilon))$ rounds. This colors all but a small fraction of edges using $\Delta+1$ colors, with no fresh colors. Partial coloring of this kind is expected to leave every vertex missing about $\epsilon\Delta$ colors.

Phase B. The repair loop then runs in rounds. In each round, every uncolored edge $(u,v)$ samples a fan at $u$ and a pair of colors $(a,b)$, biased toward colors that are popular among missing colors. It then computes its $a/b$ chain endpoint by pointer doubling on the degree-2 subgraph of colors $a$ and $b$. Each chain is labelled with an identifier, and machines sort by vertex to detect overlaps; the tuple-sorting primitive of Massively Parallel Single-Source SimRanks in O(log N) Rounds does this in $O(1)$ extra rounds. A proposal is discarded if its chain or fan shares a vertex with another proposal of higher priority. The surviving flips are applied simultaneously. We also cap chain length at $L_{\max}$: a proposer whose doubling has not terminated after $\log L_{\max}$ rounds gives up and resamples its colors, rather than tying up a long cycle.

Analysis. The analysis has two goals. The first is to bound the expected survival fraction per round, using the fact that random popular color pairs make the expected chain length small, as in the near-linear Vizing analysis, and therefore make overlaps rare. The second is to show that the abandon-and-resample rule does not stall the loop. We expect a full proof first for bounded-arboricity graphs. The density-sensitive bounds of Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring suggest that chains behave better there. General graphs we expect to support empirically first.

Baselines

The naive reference point has two parts. One is the greedy random-order coloring in MPC, which uses up to $2\Delta-1$ colors. The other is chain repair that follows each chain one step per round, with the same proposal and discard logic but no doubling.

The strongest existing parallel method is the vertex-partitioning algorithm of Streaming and Massively Parallel Algorithms for Edge Coloring. The best reported figure for it is theoretical: $\Delta+\tilde O(\Delta^{3/4})$ colors in $O(1)$ MPC rounds. We found no reported empirical color count on Lacuna for this method on any real graph. We will implement it and run it in the same simulated MPC environment as our method, with the same machine count, the same per-machine memory $n^\delta$ (for $\delta \in \{0.5, 0.7\}$), and an equal tuning budget over its group count $k$.

The second strong competitor is the $(1+\epsilon)\Delta$ nibble alone, as in Nibbling at Long Cycles, adapted to MPC. Its leftover edges get fresh colors, and $\epsilon$ is swept.

The sequential $O(m\log\Delta)$ algorithm of Vizing's Theorem in Near-Linear Time serves as a quality ceiling only, since it always reaches $\Delta+1$.

Two ablations isolate the proposal's key ingredient. The first replaces conflict discarding with full serialization, flipping one chain per round. The second replaces popular-color sampling with uniform color pairs.

We will count our method as beating the strongest baseline if two conditions hold together. Its excess colors over $\Delta$ must be at least an order of magnitude smaller than those of vertex partitioning. Its round count must stay within a small constant factor of $\log m_0\cdot\log\bar L$.

Why not just…?

Why not just use pointer jumping on the two-colored subgraph, a textbook technique? We do exactly that for a single chain, and we claim nothing new there. Pointer jumping does not decide which of many overlapping chains may flip in the same round, and serializing them costs one round per uncolored edge. The serialization ablation measures this gap directly.

Why not just follow chains step by step, given that randomized Vizing chains are short? This is a real threat. If measured chain lengths on our graphs are $O(1)$ or $O(\log\log n)$, doubling buys almost nothing. We will report the full chain-length distribution after Phase A and compare against the step-by-step baseline. If the two run in the same number of rounds, the contribution reduces to the concurrent-proposal scheme, and we would state it that way.

Why not just nibble to $(1+\epsilon)\Delta$ and stop? That route is cheap and simple, but it leaves $\epsilon\Delta$ excess colors. On high-degree social graphs this is far from $\Delta+1$. The sweep over $\epsilon$ shows how many rounds the nibble alone needs to approach our color count, if it can approach it at all.

Why not gather the leftover edges onto one machine and run sequential Vizing there? This works whenever the $\epsilon m$ leftover edges fit in $n^\delta$ memory. We will report the leftover size and use this as a hybrid baseline. Our method matters in the regime where the leftover does not fit, which is the expected case on the larger graphs in our benchmark set.

Proposed Experiments

Inputs are the SNAP graphs com-DBLP, com-LiveJournal, and com-Orkut. The last has up to 117M edges and was the scale used in Efficient and Local Parallel Random Walks. We add synthetic random regular graphs and graphs planted with long two-colored cycles as adversarial stress tests. Metrics are colors used minus $\Delta$, MPC rounds, total communication, peak machine memory, survival fraction per repair round, and chain-length distribution.

The decisive checks are three. First, the survival fraction should stay bounded away from zero across rounds; if it decays toward zero, the core claim fails. Second, the round count should scale with $\log\bar L$, not with $\bar L$, on the long-cycle stress instances. Third, the excess colors should fall to a small constant or to $O(\log\Delta)$ while the vertex-partitioning baseline sits at its $\tilde O(\Delta^{3/4})$ behavior on the same graphs.