Faster Dynamic $(\mathrm{\Delta }+1)$-Coloring Against Adaptive Adversaries

Let $v\in C=C_i$ and $s:=e_C+a_C$ such that $s⩾16/(\delta {\epsilon }^2)$. First, we argue that every $v$ with $e_v⩾2/(\delta {\epsilon }^2)$ is $\max \{\delta {\epsilon }^2/4\cdot e_v,(1-3\epsilon )/2\cdot a_v\}$-sparse. In particular, if $e_v⩾s/8$ or $a_v⩾s/24$, then $v$ is at least $(\frac{\delta {\epsilon }^2}{50}\cdot s)$-sparse.

It was already proven in [17, Lemma 6.2] that $v$ is at least $(1-3\epsilon )/2\cdot a_v$-sparse. Our definition of external degree, counting both sparse and dense neighbors outside $C$, differs from [17] so we²²2A proof of this fact has already appeared in a technical report by Halldórsson, Nolin and Tonoyan [18, Lemma 3]. Since it is a short and important proof, we include it here for completeness. prove that $v$ is at least $\delta {\epsilon }^2/4\cdot e_v$-sparse. We may assume that $G[N(v)]$ contains at least $\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{2}\right)-\delta {\epsilon }^2/2\cdot e_v\mathrm{\Delta }$ edges, for the claim otherwise trivially holds. By handshaking lemma, the number of edges in $G[N(v)]$ is

So we lower bound $|N(v)\setminus N(u)|$ for each $u\in E(v)$. If $u\in C_j\ne C$, then it has at most $\epsilon \mathrm{\Delta }$ shared neighbors with $v$, so $|N(v)\setminus N(u)|⩾(1-\epsilon )\mathrm{\Delta }$. If $u\in V_{sp}$, then $G[N(u)]$ contains at most $\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{2}\right)-\delta {\epsilon }^2\mathrm{\Delta }$ many edges by definition. On the other hand, of the edges in $G[N(v)]$, at most $|N(v)\setminus N(u)|\mathrm{\Delta }$ are not in $G[N(u)]$. Using our assumption on the number of edges in $G[N(v)]$, this means that $\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{2}\right)-\delta {\epsilon }^2/2\cdot e_v\mathrm{\Delta }⩽\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{2}\right)-\delta {\epsilon }^2{\mathrm{\Delta }}^2+|N(v)\setminus N(u)|\mathrm{\Delta }$, so that $|N(v)\setminus N(u)|⩾\delta {\epsilon }^2/2\cdot \mathrm{\Delta }$. Since all external neighbors contribute at least $\delta {\epsilon }^2/2\cdot \mathrm{\Delta }$ to the sum in Eq 1, the number of edges in $G[N(v)]$ is at most $\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{2}\right)-(\delta {\epsilon }^2/2\cdot e_v-1/2)\mathrm{\Delta }$. If $e_v⩾2/(\delta {\epsilon }^2)$, this implies that $v$ is $(\delta {\epsilon }^2/4\cdot e_v)$-sparse.

We henceforth assume that $e_v⩽s/8$ and $a_v⩽s/24$. Now, there are two cases, depending on which of $e_C$ or $a_C$ dominates.

If $e_C⩾2a_C$, then $e_v⩽s/8⩽e_C/4$. Since $\mathrm{deg}(v)+1=|C|+e_v-a_v$ holds for all vertices in $C$, it also holds on average and we get that $\mathrm{\Delta }+1⩾|C|+e_C-a_C⩾|C|+e_C/2$. Using $\mathrm{deg}(v)+1=|C|+e_v-a_v$ again, we get $\mathrm{deg}(v)⩽|C|-1+e_v⩽\mathrm{\Delta }-(e_C/2-e_v)⩽\mathrm{\Delta }-e_C/4$. Since a vertex with degree at most $\mathrm{\Delta }-x$ is $(x/2)$-sparse, $v$ is $e_C/8$-sparse, which is $s/16$-sparse.

If $e_C⩽2a_C$, then $a_v⩽s/24⩽a_C/8$. Observe that $C$ contains $a_C|C|/2$ anti-edges, of which at most $a_v\cdot 2\epsilon \mathrm{\Delta }$ may have an endpoint out of $N(v)\cap C$. So $G[N(v)\cap C]$ contains at least $a_C|C|/2-2a_v\epsilon \mathrm{\Delta }⩾a_C\mathrm{\Delta }/8$ anti-edges for . So $v$ is $a_C/8$-sparse which is $s/24$-sparse. $◀$

To maintain our sparse-denser decomposition, we use the algorithm of [4] for the almost-clique decomposition.

We can now prove that a sparser-denser decomposition can indeed be maintained.

Define $\eta =\epsilon /10$ and let $\delta$ be the universal constant such that vertices of $V_{sp}$ are $({\epsilon }^2\cdot \delta \mathrm{\Delta })$-sparse in Proposition 8. We use the algorithm of Proposition 8 with $\eta =\epsilon /10$ and define $S$ as the set containing all vertices of $V_{sp}$ and the vertices from almost-cliques $C=C_i$ with $a_C+e_C⩾\frac{50}{\delta {\epsilon }^2}\zeta$. Since we assume in Lemma 6 that $\zeta ⩽{\epsilon }^2\cdot \delta \mathrm{\Delta }$, every vertex of $V_{sp}$ is $\zeta$-sparse. Every vertex of $S\setminus V_{sp}$ is $\zeta$-sparse by Lemma 7. The remaining $\epsilon =(10\eta )$-almost-cliques are renamed $D_i$ and verify that $a_{D_i}+e_{D_i}⩽\frac{50}{\delta {\epsilon }^2}\zeta =O(\zeta /{\epsilon }^2)$ by construction. So the resulting decomposition is indeed an $(\epsilon ,\zeta )$-sparser-denser decomposition.

The algorithm of Proposition 8 already maintains the set of anti-edges in each $D_i$, so it only remains to explain how we maintain sets of external- and anti-neighbors for each denser vertex. Every time the algorithm of Proposition 8 modifies an element in $N(v)\cap V_{sp}$ or $N(v)\cap (C_1\cup \mathrm{\dots }\cup C_r)$, we inspect the change and modify $E(v)$ accordingly. Similarly, when the algorithm modifies a set of anti-edges $F_i$ by inserting or deleting some anti-edges $\{u,v\}$, we modify the sets $A(v)$ and $A(u)$ accordingly. Since each inspection (and possible modification) takes $O(\log n)$ time, it does not affect the complexity of the algorithm by more than a constant factor. $◀$

For succinctness, let $k$ denote the number of uncolored vertices in $D\cup E(v)$. Observe how the number of vertices in $D\cup E(v)$ relates to the size of the colorful matching by partitioning vertices according to their colors:

where the last inequality comes from the fact that at least $M$ colors are used by at least two vertices in $D$. Comparing the number of colors in the clique palette available to $v$ to the size of $D$ shows the contribution of redundant colors and uncolored vertices:

To complete the proof, observe that $\mathrm{deg}(v)+1=|D|+e_v-a_v$, so that $\mathrm{\Delta }+1-|D|-e_v$ simplifies to $(\mathrm{\Delta }-\mathrm{deg}(v))-a_v$. Hence, the lemma. $◀$

First, consider a call to RecolorDense(v). If $v\in I_D$, since $v$ is unmatched, recoloring $v$ does not affect the Matching Invariant; it maintains the Dense Balance Invariant because $v$ gets a color from $L(D)$, i.e., a color that is unused in $D$. If $v\notin I_D$, again since $v$ is unmatched it maintains the Matching Invariant. RecolorDense(v) colors $v$ with a color which is either unused in $D$ or used by an unmatched inlier (lines 4-5). If the color is free, the Dense Balance is maintained; if the color is used by an unmatched inlier $w$, we uncolor $w$ and call RecolorDense(w) (line 6). As we explained before, recoloring an unmatched inlier preserves invariants.

Consider now a call to RecolorMatching(u,v). Observe that it can only increase the number of matched vertices, so it maintains the Matching Invariant. It colors $u$ and $v$ with some $\chi \notin M_D$. So $\chi$ is either free or used by a unique vertex in $D$. If a vertex $w$ uses $\chi$, the algorithm uncolors $w$ and calls RecolorDense(w) (line 6), which maintains the invariants as we previously explained.

Finally, a call to RecolorSparse(v) where $v\in S$ recolors $v$, which does not affect the invariants. It may steal a color to one denser neighbor $w$. If $w$ is unmatched RecolorDense(w) maintains the invariant. If $w$ is matched, the algorithm calls RecolorMatching(w, matched[w]) which can only end if $w$ and its matched vertex are same-colored. So the call to RecolorSparse maintains the invariants. $◀$

Lemma 13 shows that RecolorInsert and RecolorDelete maintain the Dense Balance Invariant since it is only affected when vertices are recolored. On the other hand, the Matching Invariant depends on the values of $|M_D|$ and $a_D$, which are affected by insertions or deletions of edges.

Assume that when the algorithm reaches line 2 of RecolorDelete or line 9 of RecolorInsert. It must be that $|M_D|=\lfloor 8\cdot a_D\rfloor -1$ because the invariant held before the update and

• $\mathrm{■}$

  inserting an edge cannot increase $a_D$ and may decrease $M_D$ by one if the edge inserted was between matched vertices (line 6);

• $\mathrm{■}$

  deleting an edge may increase $a_D$ by $2/|D|$, which means $\lfloor 8a_D\rfloor$ increases by at most one, while $M_D$ does not change.

In either case IncrMatching is called before RecolorDelete ends or RecolorInsert reaches line 10. In order to end, IncrMatching matches a new pair $\{u,v\}$ of previously unmatched vertices and calls RecolorMatching(u,v) (line 12 in Algorithm 4). Then RecolorMatching(u,v) ends only after same-coloring $u$ and $v$ (line 8 in Algorithm 4), so the updated matching has size $\lfloor 8\cdot a_D\rfloor$. The Dense Balance Invariant holds when the algorithms call IncrMatching (because it held before the update and uncoloring vertices does not affect it) and calls to RecolorMatching and RecolorDense preserve it (Lemma 13). $◀$

Suppose first that $v$ is an inlier, i.e., such that $a_v⩽8a_D$ and $e_v⩽8e_D$. We claim that every inlier has an available color in $L(D)\setminus \phi [E(v)]$. Observe that this set is exactly $L(D)\cap L(v)$. Under the Matching Invariant, at least $|M_D|⩾\lfloor 8a_D\rfloor$ colors are repeated in $D$ and since $v$ is uncolored, the accounting lemma (Lemma 10) implies that

where the second inequality uses the assumption that $a_v⩽8a_D$ and $a_v$ is an integer. To find this color, the algorithm loops over vertices of $E(v)$ and constructs the set $\phi [E(v)]$ in $O(e_v\log n)⩽O(\zeta \log n)$ time. Then it loops over $L(D)$ and stops when it finds a color that is not in $\phi [E(v)]$. If $L(D)$ contains more than $8e_D⩾e_v$ colors, the algorithm finds a color after $O(e_D\log n)⩽O(\zeta \log n)$ time. Otherwise, the algorithm goes over at most $8e_D⩽O(\zeta )$ colors; hence ends in $O(\zeta \log n)$ time.

Suppose now that $v$ is an outlier. The algorithm samples colors in $[\mathrm{\Delta }+1]$ until it finds one that is not used by (1) a matched vertex, (2) an external neighbor, or (3) an outlier. That is a color not in $M_D\cup \phi [E(v)\cup O_D]$ (lines 4-5). We claim that this set contains at most $\mathrm{\Delta }/2$ colors. At most $2\epsilon \mathrm{\Delta }$ colors are used by an external neighbors of $v$. By Markov’s inequality, the number of vertices with $a_v>8a_D$ or $e_v>8e_D$ is at most $|C|/4⩽(1/4+\epsilon )\mathrm{\Delta }$. Finally, observe that we always have $|M_D|⩽8\cdot 3\epsilon \mathrm{\Delta }$. Indeed, RecolorInsert and RecolorDelete call IncrMatching only when because $a_D⩽3\epsilon \mathrm{\Delta }$. Calls to RecolorMatching(u,v) where $u$ and $v$ are already matched do not increase the matching size. Adding these up, at most $(1/4+27\epsilon )\mathrm{\Delta }⩽\mathrm{\Delta }/2$ colors are blocked by $M_D\cup \phi (E(v)\cup O_D)$ for $\epsilon ⩽1/108$. A random color in $[\mathrm{\Delta }+1]$ therefore works w.p. $1/2$, so the probability that the algorithm tries more than $c\log n$ random colors is $n^{-c}$. To verify if a random color works, the algorithm iterates through its color class in $O({\max }_{\chi }|\mathrm{\Phi }[\chi ]|\log n)$ time. Then, there might be a additional call to RecolorDense(u) where $u\in I_D$, which results in the claimed runtime. $◀$

RecolorMatching colors $u$ and $v$ the same way RecolorDense colors an outlier. The complexity of recoloring an unmatched denser vertex (line 8) is upper bounded by Lemma 15. So we obtain the following lemma:

It remains to bound the time spent on fixing the matching size with IncrMatching.

We may assume that $a_D>1/8$ since otherwise the Matching Invariant holds even with an empty matching. In particular, $F_D$ is not empty. If , at least $|F_D|/2$ anti-edges of $F_D$ have both endpoints unmatched because $F_D$ contains $a_D|D|/2$ anti-edges while the current colorful matching is incident to at most of them for, say, $\epsilon ⩽1/100$. The probability that IncrMatching samples $c\log n$ anti-edges in $F_D$ without finding any with both endpoints available is thus $n^{-c}$. Lemma 16 then implies the result. $◀$

Call $R$ the set of colors used by at least two denser neighbors of $v$. The algorithm samples colors in $[\mathrm{\Delta }+1]$ until it finds one in $L_S(v)\setminus R$ and we claim that this set contains at least $t$ colors at all time. It is easy to verify that $|R|⩽|L(v)|$, where $L(v):=[\mathrm{\Delta }+1]\setminus \phi (N(v))$ is the set of available colors, hence that $|L_S(v)\setminus R|⩾|R|$ because $L(v)\subseteq L_S(v)\setminus R$. So we may assume that $|R|⩽t$. Now, since RefreshColoring succeeded (Proposition 11), we have $|L_S(v)|⩾3t$ when the phase begins. As each update recolors at most one sparser vertex, after $i⩽t$ updates, we have that $|L_S(v)\setminus R|⩾3t-i-|R|⩾t$.

Each random color trial (line 2 in Algorithm 2) recolors $v$ with probability at least

Hence, w.h.p., the algorithm samples $O(\mathrm{\Delta }\log n/\zeta )$ colors before finding one that fits. To verify if a color $\chi$ is suitable for recoloring $v$, the algorithm iterates through vertices of $\mathrm{\Phi }[\chi ]$ and checks if they belong to $N_S(v)$ or $N_{V\setminus S}(v)$ in $O(\log n)$ time. Overall, finding a suitable $\chi$ takes $O\left(\mathrm{\Delta }/\zeta \cdot {\max }_{\chi }|\mathrm{\Phi }[\chi ]|{\log }^{2}n\right)$ time. Then, if there is a $w\in N_{V\setminus S}(v)$ with color $\chi$, RecolorSparse makes one call to RecolorDense(w) or RecolorMatching(w, matched[w]) which recolors $w$ in $O(\zeta \log n+{\max }_{\chi }|\mathrm{\Phi }[\chi ]|{\log }^{2}n)$ time by Lemmas 15 and 16. $◀$

Overall, our algorithm is efficient only if we can maintain small enough color classes. The Dense Balance property ensures that denser vertices contribute $O(n/\mathrm{\Delta })$ to each color class. The contribution of vertices in $S$ is accounted for separately, using an argument over the randomness of the entire phase:

Fix $i⩽t$. We show that Eq 3 holds before the $i$-th update of this phase with high probability. Fix $\chi \in [\mathrm{\Delta }+1]$ and count the number of sparser vertices to join $\mathrm{\Phi }[\chi ]$ during this phase. Define $X_j$ to indicate if, during the $j$-th update, a sparser vertex joins $\mathrm{\Phi }[\chi ]$. Observe that, by the success of RefreshColoring, RecolorSparse colors $v$ with a uniform color from a set of at least $\gamma \cdot \zeta$ colors, regardless of the recolorings that occurred earlier in the phase. Hence, the probability that it recolors $v$ with $\chi$ is $𝔼[X_j|X_1,\mathrm{\dots },X_{j-1}]⩽O(1/\zeta )$. By the Chernoff bound with stochastic domination (Lemma 24), we have ${\sum }_{j\in [i]}{X}_j⩽O(i/\zeta )+O(\log n)$ with high probability. So before the $i$-th update, the set $\mathrm{\Phi }[\chi ]$ contains the $O(n/\zeta )$ vertices initially present after RefreshColoring (Sparse Balance property in Proposition 11) and at most $O(i/\zeta +\log n)$ new ones. This holds for all $i\in [t]$ by union bound and thus implies the lemma. $◀$