Template Nibbling for Dynamic Edge Coloring on Real Graphs

Edge coloring gives every edge of a graph a color so that no two edges meeting at a vertex share one. It is the combinatorial core of scheduling problems in which each edge is a job that needs two resources at once, such as link scheduling or the rounds of a switch. When the graph changes over time, the key cost is recourse: how many existing edges must be recolored after each insertion or deletion. Theory has recently shown that the nibble method can make recourse constant. The nibble method colors a graph in cautious rounds, in each of which every uncolored edge tentatively tries a random color and keeps it only if no neighbor tried the same one. Theory has also shown that algorithms which only shift colors along paths cannot reach constant recourse. None of this has ever been run on a single graph. The optimal-time algorithm hides constants of order $10^{10}$ at $\epsilon=0.1$, and its analysis depends on an elaborate graph-splitting step that exists only to neutralize short cycles.

This note proposes building and measuring a stripped-down template nibble for dynamic edge coloring with a $(1+\epsilon)\Delta$ palette, where $\Delta$ is the maximum degree. All random choices are fixed in advance, so after any update the algorithm recomputes only the "ripple" of edges whose outcome changed. The proposal asks two empirical questions that theory cannot answer. First, on real clustered networks, do ripples stay small without the cycle-breaking machinery? Second, does the recourse advantage that nibbling has over shift-based repair actually appear, and if so where? A side property comes nearly free: a template coloring is a function of the current graph and the seed, not of the update history. That history-independence is the same "consistency" property that systems work has had to engineer by hand for vertex coloring.

Core Claim

We claim that a practical template nibble can dispense with subsampling. It should use a few nibble rounds, fixed per-edge random choices, and a cheap greedy-plus-repair pass for the few edges left uncolored. On real-world graphs, most edges touch low-degree vertices with abundant spare colors, so ripples should be short. The cases theory worries about, short cycles and palette pressure, concentrate around the few hub vertices. Our specific falsifiable prediction is about hub-incident updates. There, template nibbling should cut the tail recourse (99th percentile and maximum) below that of Vizing-chain and fan-based repair, at comparable color count and within a small constant factor of repair's wall-clock time. It should also produce history-independent colorings, which shift-based repair cannot.

If ripples blow up on high-clustering graphs, that is an equally valuable finding. It would be the first empirical evidence that the cycle-breaking step in the theory is doing real work rather than serving only as a proof device.

Relation to Prior Work

The method comes from the nibble lineage. Near-Optimal, Distributed Edge Colouring via the Nibble Method introduced the tentative-choose, keep-if-unconflicted round structure. Online Edge Coloring Algorithms via the Nibble Method adapted it to random-order online arrivals. Nibbling at Long Cycles made it dynamic by pre-fixing random choices and recomputing ripples. That paper obtains $O(\log^4(1/\epsilon)/\epsilon^9)$ worst-case expected update time when $\Delta=\Omega_\epsilon(\text{polylog}\,n)$. It first splits the graph into subgraphs whose neighborhoods look like trees, because short cycles couple the color palettes of nearby edges. We reuse its template-and-ripple idea directly. We depart from it by treating subsampling as an optional component to be tested by ablation, and by dropping the degree threshold, since real graphs violate it at almost every vertex except the hubs.

The motivation for testing the separation comes from Beyond Vizing Chains. It proves that algorithms which only shift colors along paths face recourse lower bounds that nibbling can beat in principle. It contains no experiments, and its shift-tree search costs $O(m+\Delta^2)$ per update. Arboricity-Dependent Algorithms for Edge Coloring and Vizing's Theorem in Near-Linear Time are likewise purely theoretical, and the latter's separable collections of fans are the kind of structure the survey literature flags as a heavy engineering burden.

The empirical constraints come from the experimental dynamic-graph literature. Recent Advances in Fully Dynamic Graph Algorithms reports that sophisticated dynamic algorithms are rarely implemented and often lose to simple ones. Faster Fully Dynamic Transitive Closure in Practice found its simplest variant, SV(1), to be the fastest and most robust. Fully Dynamic Single-Source Reachability in Practice found a simplified Even-Shiloach variant beating multi-level structures, and deletions up to 50 times slower than insertions. These results are a warning that our nibble may lose to plain repair, and the experiment is designed so that it can lose visibly. Dynamic Matching Algorithms in Practice supplies our methodology: implement the theory, add practical relaxations, and simulate deletions by undoing updates when real deletion streams are missing.

For vertex coloring, Effective and Efficient Dynamic Graph Coloring built DC*, a degree-ordered greedy propagation scheme. It is deterministic by construction and yields consistent colorings for the same final graph. We seek the analogous consistency for edge coloring through randomness fixed in advance, rather than through a global ordering. The randomized dynamic vertex colorers Dynamic Algorithms for Graph Coloring and Constant-Time Dynamic (Δ+1)-Coloring are also unimplemented. They are out of scope here except as evidence that the whole randomized dynamic coloring line lacks measurement.

Research Program

We will build three things. The first is a static nibble in the round structure of the online and dynamic papers. Each edge $e$ holds a pre-drawn sequence of pairs (the round in which it activates, and its candidate color). It runs for $R$ rounds, with $R$ between 3 and 10, and a final pass colors leftover edges greedily, falling back to a Vizing chain. The second is the dynamic ripple engine. After an update it marks the edges whose round-$r$ outcome could have changed. It then propagates changes forward round by round, recoloring only edges whose final color differs. This makes the maintained coloring identical to the static nibble run on the current graph with the same seed.

The third is an optional subsampling layer. It splits edges at random into $k$ groups with disjoint slices of the palette, a simple rendition of the cycle-breaking idea. It exists so that its contribution can be measured rather than assumed.

The analysis instruments every ripple. We record its size, its depth in rounds, the degrees of the endpoints involved, and the local clustering around the updated edge. This lets us check directly whether ripple blowup is driven by short cycles, as the theory's design implies, or by palette pressure at hubs. We sweep $\epsilon$ over 0.05, 0.1, 0.2 and 0.5 and plot measured recourse against $\epsilon$. That plot shows how far the observed dependence is from the worst-case $1/\epsilon^9$.

Baselines

The naive reference is static recomputation. After each update we rerun a fast static edge colorer from scratch: greedy with a $(2\Delta-1)$ palette, and our own static nibble with the same palette as the dynamic method. Recourse is the Hamming distance between consecutive colorings. This matches how Dynamic Matching Algorithms in Practice measured its factor-of-12 speedup of dynamic optimum matching over recomputing from scratch. That number concerns matching, not coloring. It serves only as a rough sense of what dynamic maintenance usually gains.

The strongest competitor is local repair. On insertion of an edge $(u,v)$, it takes any color free at both endpoints within the $(1+\epsilon)\Delta$ palette. If none exists, it applies a Misra-Gries fan and Vizing-chain flip. On deletion, it does nothing. This is the shift-based family that Beyond Vizing Chains bounds from below. On power-law graphs it will hit the free-common-color case almost always, so it is the honest bar to beat. We will also implement a bounded-budget version of that paper's shift-tree search, capped at the same per-update time budget as the nibble engine.

No reported result was found on Lacuna for dynamic edge coloring recourse, color count, or update time on any real-world graph. The closest reported numbers are for vertex coloring. Effective and Efficient Dynamic Graph Coloring reports that DC* uses "around 30-40 colors" on Flickr versus "50-60" for DC-Local, and runs "at least three orders of magnitude faster than Global" per update. We cite these only as a calibration of what a well-engineered dynamic colorer achieves over recomputation.

All methods run in one C++ codebase, on the same machine, on the same update streams, with identical adjacency and palette data structures. Each method gets the same tuning budget: a grid over its own two or three parameters on a held-out graph.

Two ablations isolate the key ingredient. The first draws fresh randomness at every update instead of using the template. This removes history-independence and should increase recourse if the template matters. The second toggles subsampling on and off.

Beating local repair means lower 99th-percentile and maximum recourse on hub-incident updates, at no more than 5% more colors, with median update time within 10 times that of repair. Merely matching repair's mean recourse is not enough, because both methods should be near zero on typical updates.

Why not just…?

Why not just use greedy insertion with Vizing-chain repair? This is the real threat. On graphs whose degrees follow a power law, nearly every insertion touches a low-degree vertex, so a free common color exists and recourse is zero. We therefore do not claim an advantage on average-case updates. The experiments report recourse separately for updates whose endpoints both exceed the 99th degree percentile. Those are the updates where fans and chains grow long. If repair also stays flat there, the honest conclusion is that nibbling's theoretical advantage does not show up in practice, and we will report it as such.

Why not just recompute a static coloring after each update? Recomputation fails on recourse, not only on time. Two independent static colorings of nearly identical graphs share few colors, so every update recolors a large fraction of edges. Dynamic transitive-closure experiments found static BFS and DFS "orders of magnitude slower" than dynamic methods (Faster Fully Dynamic Transitive Closure in Practice). Our recomputation baseline will show whether the same holds here.

Why not just implement the full algorithm of Nibbling at Long Cycles faithfully? Its parameters are set for worst-case proofs that require $\Delta=\Omega_\epsilon(\text{polylog}\,n)$ at every vertex, which real graphs violate. Its constants are prohibitive. The experimental literature consistently finds that simplified variants win (Fully Dynamic Single-Source Reachability in Practice). The subsampling ablation is exactly the test of whether the faithful version's extra machinery helps. We keep it as a component so that it is measured rather than dismissed.

Why not just adapt DC*'s ordered greedy propagation to edges? Ordered greedy gives consistency, but it relies on propagation cascades whose length has no bound. It has no recourse guarantee even in theory. We include an edge analogue, which orders edges by endpoint degree and colors each greedily, as an additional consistent baseline. Comparing it against the template nibble on history-independence and tail recourse settles whether randomness buys anything beyond what an ordering provides.

Proposed Experiments

The datasets follow the prior experimental studies. We use the six KONECT Wikipedia hyperlink networks, treated as undirected, together with their shuffled variants. We add AS-CAIDA snapshots and the ten real graphs used for DC*, from MovieLens to WikiEnglish, with Flickr and WikiTalk as the large, hub-heavy cases. Synthetic families are Erdős-Rényi graphs at $n=10^5$ and $10^7$, Kronecker graphs in both constant-size and growing variants, and uniform-degree graphs. Where real deletions are absent, we simulate them by undoing a fixed fraction of insertions, as in the matching study, and flag those results as simulated.

The metrics are the number of colors divided by $\Delta$; recourse per update (mean, 99th percentile and maximum), split by endpoint-degree class; wall-clock time per update, including deletion/insertion asymmetry; and memory. History-independence is measured as the fraction of edges colored differently when the same final graph is reached through five random permutations of the update stream.

Three checks decide the proposal.

The first check is whether ripple size, with subsampling off, correlates with local clustering. If it does, and switching subsampling on removes the correlation, then the theory's cycle-breaking step is necessary in practice.

The second check is whether template nibbling beats bounded local repair on hub-incident tail recourse at matched color count. That comparison is the first empirical test of the separation shown in Beyond Vizing Chains.

The third check plots measured recourse and update time against $\epsilon$. Its slope, compared with the $1/\epsilon^9$ worst-case bound, quantifies how pessimistic that bound is on real graphs.