Colorful Vertex Recoloring of Bipartite Graphs

First observe that once a vertex becomes special, then it is always colored by a special color. Likewise, only special vertices are colored by special colors.
Algorithm $ℬ$
State: $\mathrm{■}$ Each vertex $u$ has an actual color $c\left(u\right)$ and a simulated color $\overline{c}\left(u\right)$. The simulated coloring $\overline{c}$ is the coloring maintained by the simulation of $𝒜$. The initial actual colors are given as input, and the initial simulated colors are the initial actual colors. $\mathrm{■}$ Each vertex records whether its simulated color was ever changed by the simulation of $𝒜$. This allows the algorithm to maintain the set $R_i$. $\mathrm{■}$ Each vertex has an indication whether it is “special” or not. Initially all vertices are not special.
Action:
Upon the arrival of edge $e_i=(u_i,v_i)$:  a. If ${\sigma }_{i-1}^{\mathrm{sim}}\circ e_i$ is $(D,\alpha )$-moderate then
   send $e_i$ to $𝒜$ (which updates $\overline{c}(\cdot )$); //${\sigma }_i^{\mathrm{sim}}={\sigma }_{i-1}^{\mathrm{sim}}\circ e_i$
   set $c\left(w\right):=\overline{c}\left(w\right)$ for every non-special vertex $w$.  b. Else
  If both $u_i$ and $v_i$ are not special then mark $u_i$ as special.  c. Invoke $\text{recx}(u_i,v_i)$
Procedure $\text{recx}(u,v)$: 1. If $u$ and $v$ are special then
   if $e=(u,v)$ is monochromatic then
     recolor $u$ with a free special color. // there are $\mathrm{\Delta }+1$ special colors 2. Else
   If $u$ is special then
     if $u$ is colored by a basic color then
       recolor $u$ with a free special color. // first time $u$ is colored special 3. Else
     If $v$ is special then // this case cannot happen because of the way recx is used.
       if $v$ is colored by a basic color then
        recolor $v$ with a free special color.

We prove the lemma by induction on $i$. The base case is $i=0$, in which $E_0=\mathrm{\varnothing }$ and hence any coloring is valid. For the inductive step, we first consider all edges but the new edge $e_i$ and for those we proceed in two sub-steps. Then we consider the new edge $e_i$.

For all edges but $e_i$, if $e_i$ is not a simulated edge and is not sent to $𝒜$, then the first sub-step is empty. If $e_i$ is a simulated edge and is sent to $𝒜$, then the colors of some non-special vertices may change. After this sub-step, for each (old) edge: (1) if its two endpoints are non-special then the edge is not monochromatic by the correctness of $𝒜$; (2) if its two endpoints are special, then their color does not change in this sub-step and the edge is not monochromatic by the induction hypothesis; (3) if one endpoint is special and the other is not, then one and only one endpoint is colored by a special color, and hence the edge is not monochromatic.

The second sub-step is the invocation of recx on the input edge. Following this invocation one vertex might be recolored to a special color. Clearly any (old) edge with at least one node not special remains non-monochromatic by the induction hypothesis. For an (old) edge with two special endpoints, if their color is not changed, they remain non-monochromatic by the induction hypothesis. For such an edge for which one of its endpoints changed color by recx, the code ensures that it is non-monochromatic after the execution of recx.

Now as to the edge $e_i$ itself, we have a number of cases depending whether it is a simulated edge and the status (special or not) of its two endpoints when step $i$ begins.

1. 1.

   If its two endpoints are non-special when step $i$ starts:

   • $\mathrm{■}$

     if $e_i$ is a simulated edge: at the end of the first sub-step $e_i$ is not monochromatic by the correctness of $𝒜$; none of its endpoints is marked special and hence recx does not recolor any node and $e_i$ remains non-monochromatic.

   • $\mathrm{■}$

     if $e_i$ is not a simulated edge: One of its endpoints is marked special; recx recolors that vertex by a special color, while the other endpoint remains colored by a basic color; hence $e_i$ is not monochromatic.

2. 2.

   If its two endpoints are special when step $i$ starts, then regardless of whether $e_i$ is a simulated edge or not the code of recx ensures that $e_i$ is not monochromatic.

3. 3.

   If one endpoint is special and the other is not when step $i$ starts, then regardless of whether $e_i$ is a simulated edge or not, the status of neither vertex changes, and one of them remains colored by a special color and the other by a basic color, hence $e_i$ is not monochromatic.

$◀$

We now turn to analyze the competitiveness of our algorithm. To this end, we first prove the following property about graphs with bounded bond size.

Consider the multi-graph $G^{\prime }=(V^{\prime },E^{\prime })$ obtained from $G$ by contracting each $V_i$ to a single node and eliminating self-loops. We shall prove that $|E^{\prime }|\le (k-1)\beta$.

First, we note that $|V^{\prime }|=k$, and that the size of the largest bond of $G^{\prime }$ is at most $\beta$. We now prove, by induction on $k$, that if a loop-free multigraph $G^{\prime }=(V^{\prime },E^{\prime })$ has $k$ nodes and bond size at most $\beta$, then $|E^{\prime }|\le (k-1)\beta$. The base case is $k=1$; in this case, $E^{\prime }$ is empty since $G^{\prime }$ does not contain self loops.

For the inductive step, fix any $k\ge 2$. Let $v$ be an arbitrary node in $V^{\prime }$, and let $\overline{V}=V^{\prime }\setminus \left\{v\right\}$. We proceed according to the connectivity of $\overline{V}$. If $G^{\prime }[\overline{V}]$ is connected, then the degree of $v$ is at most $\beta$. Since $|\overline{V}|=k-1$, by the induction hypothesis and the fact that the size of the largest bond of $G^{\prime }[\overline{V}]$ is at most the size of the largest bond of $G^{\prime }$ (which is at most $\beta$), we have that $|E^{\prime }|\le \beta +(k-2)\beta =(k-1)\beta$.

Otherwise, $G^{\prime }[\overline{V}]$ is disconnected. Let $C_1$ be the set of vertices of an arbitrary connected component of $\overline{V}$, and denote $C_2=\overline{V}\setminus C_1$. Let $C_1^v=C_1\cup \{v\}$, and $C_2^v=C_2\cup \{v\}$. Trivially $|C_1^v|+|C_2^v|=k+1$, and $m_1+m_2=|E^{\prime }|$, where $m_1$ and $m_2$ are the number of edges in $G^{\prime }[C_1^v]$ and in $G^{\prime }[C_2^v]$, respectively. Since the largest bond of a subgraph is no larger than the largest bond of the original graph, and since the number of nodes in each of $G^{\prime }[C_1^v]$ and $G^{\prime }[C_2^v]$ is strictly less than $k$, by the inductive hypothesis we have that $m_1\le (|C_1^v|-1)\beta$ and $m_2\le (|C_2^v|-1)\beta$. It follows that $|E^{\prime }|=m_1+m_2\le (k-1)\beta$. $◀$

Let $V_1,\mathrm{\dots },V_k,V_{k+1}$ be any partition of $V$ such that:

• $\mathrm{■}$

  for each $1\le i\le k$, $C_i\subseteq V_i$, and $G[C_i]$ is connected; and

• $\mathrm{■}$

  $V_{k+1}$ is exactly the set of vertices which are not connected in $G$ to any vertex of ${\bigcup }_{i=1}^k{C}_i$.

This can be achieved by associating each vertex of $V\setminus V_{k+1}$ with the set $C_i$ closest to it (like in a Voronoi partition). Note that we may assume without loss of generality that $V_{k+1}$ is empty: otherwise, consider the graph $G^{\prime }\stackrel{\mathrm{def}}{=}G[V\setminus V_{k+1}]$: Clearly, by the definition of $V_{k+1}$, the number of edges connecting vertices in different $C_i$ in $G$ and $G^{\prime }$ is the same.

Since every edge between two subsets $C_i,C_j$ connects different parts of the partition $V_i$ and $V_j$, the result follows from Lemma 10, when applied to each connected component of $G$ separately. $◀$

We proceed to bound from above the cost of Algorithm $ℬ$. The cost consists of two parts: the cost incurred by Procedure recx and the cost due to the simulation of $𝒜$. We start by stating a number of facts due to the definition of the algorithm.

Observe that a node $v$ is colored by a special color only in procedure recx, when it is a special vertex. Moreover, it is marked special only when an edge $e_j=(v,u)$ arrives, and that edge is in $E\setminus E_{\mathrm{sim}}$. It follows that there is an edge $e_j$, for $j\le i$, which connects two large and heavy connected components of $E{[j-1]}_{\mathrm{sim}}$. Hence, $v$ is part of a large connected component of $E{[j-1]}_{\mathrm{sim}}$ which has more than $\alpha D$ vertices of $R$. $◀$

Recalling the sequences ${\sigma }^{\mathrm{exc}}$ and ${\sigma }^{\mathrm{sim}}$ defined in Definition 8 as a function of any sequence $\sigma$, we prove the following lemma that allows us to (indirectly) give an upper bound on the number of vertices that require “special treatment”.

In order to prove the lemma we maintain, as the input sequence ${\sigma }^{\mathrm{sim}}$ proceeds, sets of vertices, $B_1,B_2,\mathrm{\dots },B_s$, which are pairwise disjoint; furthermore, all vertices in each $B_i$ belong to the same connected component of the input graph (with respect to all edges, not only those in ${\sigma }^{\mathrm{sim}}$). We call the $B_i$ sets witness sets. We construct the witness sets online as follows. Initially, there are no witness sets. When an edge $e=(u,v)\in \sigma$ arrives, we modify the witness sets as follows.

1. I

   If none of $\{u,v\}$ is already in one of the existing witness sets, and if the connected component that contains $e$ (after $e$ is added to the graph) has at most $\alpha D$ vertices from $R$: do nothing.

2. II

   If none of $\{u,v\}$ is already in one of the existing witness sets, and if the connected component that contains $e$ (after $e$ is added to the graph) has more than $\alpha D$ vertices from $R$: create a witness set which contains all the vertices in that connected component.

3. III

   If one of $\{u,v\}$, w.l.o.g. $u$, is already in an existing witness set, say $B$, and $v$ is not: add all the vertices of the connected component of $v$ to $B$. (As we prove below in Point 4, these vertices do not yet belong to any witness set.)

4. IV

   If both $\{u,v\}$ are already in some witness sets (possibly the same one): do nothing.

Intuitively, witness sets are created when a connected component passes the “critical mass” threshold of $\alpha D$ vertices from $R$, and vertices that do not belong to any witness set are added to the witness set they encounter, i.e., the set of the first vertex that belongs to a witness set, to which they are connected.

The following properties follow from a straightforward induction on the input sequence.

1. 1.

   All the vertices of a given witness set are in the same connected component of $\sigma$. This is because a new witness set is created from connected vertices. Moreover, additions to a witness set are always in the form of vertices connected to vertices already in that witness set.

2. 2.

   All the vertices in a connected component of ${\sigma }^{\mathrm{sim}}$ with more than $\alpha D$ vertices of $R$ are in some witness set (not necessarily all in the same witness set). This follows by induction on the arrival of new edges of ${\sigma }^{\mathrm{sim}}$ and the actions relative to witness sets taken when this happens.

3. 3.

   Every two vertices $u,v$ which are in the same connected component of $\sigma$ are either both in some witness set (not necessarily the same), or both are not in any witness set. This follows from the fact that the actions taken regarding witness sets exclude the possibility of an edge with exactly one endpoint in a witness set.

4. 4.

   If a vertex $w$ belongs to some witness set $B$ at some point of the execution, then $w$ belongs to $B$ in the remainder of the execution. This follows from the fact that a vertex $w$ becomes a member of witness set $B^{\prime }$ only in Cases II or III above.

   In Case II, $w$ did not belong before to any witness set because both $u$ and $v$ did not belong to any witness set and $w$ is in the same connected component of either $u$ or $v$. Hence, by Point 3, $w$ is not in any witness set.

   In Case III, similarily, $w$ is connected to $v$ and since $v$ does not belong to any witness set, then by Point 3 $w$ is not in any witness set.

It follows from the above properties that the total number of witness sets is at most $\frac{|R|}{\alpha D}$, because each witness set that is created requires at least $\alpha D$ distinct vertices of $R$, vertices do not change their witness set, and the sets are pairwise disjoint.

Next, we claim that when an edge $e$ is added to ${\sigma }^{\mathrm{exc}}$ (i.e., it connects two distinct large-and-heavy connected components $C,C^{\prime }$ of ${\sigma }^{\mathrm{sim}}$), then the vertices of $C$ and $C^{\prime }$ already belong to two distinct witness sets. By definition, each of $C$ and $C^{\prime }$ contains more than $\alpha D$ vertices of $R$, and hence, by Point (2) above, the endpoints of $e$ are already associated with witness sets. To show that the endpoints of $e$ belong to distinct witness sets, assume, by way of contradiction, that the endpoints of $e$ belong to the same witness set. Then from Point 1 we have that $C$ and $C^{\prime }$ are already connected in $\sigma$ (but, by assumption, they are not connected in ${\sigma }^{\mathrm{sim}}$). Let $e_0$ be the first edge (according to the order of the arrival of the edges) in ${\sigma }^{\mathrm{exc}}$ that completes a path from some node in $C$ to some node in $C^{\prime }$. Since $e_0\notin {\sigma }^{\mathrm{sim}}$, it must be the case that when $e_0$ arrived, both of its endpoints belonged to two large and heavy connected components of ${\sigma }^{\mathrm{sim}}$. Point 2 ensures then that the vertices of $C$ and $C^{\prime }$ are already in witness sets. Point 1 implies that these witness sets must be distinct, because before the arrival of $e_0$, $C$ and $C^{\prime }$ are not connected to each other in $\sigma$. The sets to which the vertices of $C$ and $C^{\prime }$ belong are the same, and hence distinct, when $e$ arrives, by Point 4. This is in contradiction to the assumption that the witness sets are the same.

Thus, an edge is added to ${\sigma }^{\mathrm{exc}}$ only when its endpoints are in two distinct witness sets. Since there can be at most $\frac{|R|}{\alpha D}$ such sets, we get from Corollary 11 and the assumption that the graph has bond size at most $\beta$, that there are at most $\frac{\beta |R|}{\alpha D}$ such edges. $◀$

Procedure recx only recolors vertices that are marked special. For each special vertex $v$, the procedure recx recolors $v$ from a basic color to a special color exactly once in the step when $v$ becomes special, and might recolor $v$ again when a new edge $(v,u)$ arrives, and also $u$ is marked special. Let $V^{\prime }$ be the set of vertices ever marked special, and $E^{\prime }$ the set of edges such that when they arrive both their endpoints are marked special.

A node $v$ is marked special only when an edge $e_i=(v,u)$ arrives and $e_i\in E\setminus E_{\mathrm{sim}}$. By Lemma 13 $|E\setminus E_{\mathrm{sim}}|\le O(\frac{\beta |R|}{\alpha D})$, and hence $|V^{\prime }|\le O(\frac{\beta |R|}{\alpha D})$.

Let $|V^{\prime }|=\mathrm{\ell }$, and $V^{\prime }=\{u_j:1\le j\le \mathrm{\ell }\}$. By applying Corollary 11 with sets $C_1=\{u_1\},\mathrm{\dots },C_{\mathrm{\ell }}=\{u_{\mathrm{\ell }}\}$, we have that $|E^{\prime }|\le O(\frac{{\beta }^2|R|}{\alpha D})$.

The cost of recx is therefore $O(|V^{\prime }|+|E^{\prime }|)\cdot D=O(\frac{\beta |R|}{\alpha D}+\frac{{\beta }^2|R|}{\alpha D})\cdot D=O(\frac{{\beta }^2|R|}{\alpha }).$ $◀$

Next, we bound from above the cost incurred by the simulation of $𝒜$. We need a refined analysis of Algorithm $𝒜$. In the following two lemmas, we recall properties of $𝒜$ from [1]. The first lemma relates the number of vertices recolored by $𝒜$ to the optimal cost.

The next lemma is used to upper-bound the number of times a vertex is recolored by $𝒜$.

In [1], Lemma 15 and Lemma 16 are used to show an $O(\log n)$ bound on the competitive ratio of $𝒜$. Here, we prove a tighter bound on the competitive ratio when the input sequence is moderate (cf. Definition 7). The proof uses amortized analysis by designing an appropriate charging scheme.

Let $R_i$ be the set of vertices recolored by $𝒜$ so far after it processed the $i$th input edge. Let $I^{+}$ be the subset of steps given by Lemma 16; it suffices to bound from above the cost incurred by $𝒜$ on steps in $I^{+}$. We will do this via a charging scheme.

The high-level intuition behind the charging scheme is as follows. Let $i\in I^{+}$, and suppose $e_i$ connects components $C_i$ and $C_i^{\prime }$, and that in response, $𝒜$ recolors $C_i$ (recall that we consider bipartite graphs and two colors, hence a monochromatic edge must connect two distinct connected components). Our goal is to charge a the load of $1$ on certain vertices and show that (1) the total charge in each step $i$ is at least a constant fraction of $|C_i\cap R|$ or $|C_i^{\prime }\cap R|$ and (2) every vertex is charged $O(\log D)$ times in total over the course of the input sequence. There are four cases to consider and each case will use a different type of charging. (1) The first is when $C_i$ is small, i.e. $|C_i|\le D$. In this case, we charge every vertex in $C_i$. Lemma 16 implies that a vertex can only be charged by this charging type a total of $O(\log D)$ times. (2) The second case is when $C_i$ is large and light. In this case, we charge to the vertices of $C_i$ that are newly recolored by the algorithm. Since $C_i$ is light, the number of vertices that are recolored for the first time by $𝒜$ in this step is sufficiently large. Since this type of charging charges newly recolored vertices, a vertex can be charged by this charging type at most once.

The remaining possibilities concern case (3) when $C_i$ is large and heavy. We consider two subcases. (3.1) The first subcase is when $C_i$ is large and heavy and $C_i^{\prime }$ is small and heavy. In this case, we charge to $C_i^{\prime }\cap R$. Lemma 16 implies that $|R\cap C_i^{\prime }|$ is at least an $\alpha$ fraction of $|C_i|$. Moreover, since the vertices in $C_i^{\prime }$ are part of a large component after this step, a vertex can be charged by this charging type at most once. The final and most interesting case is (3.2) when $C_i^{\prime }$ is light. To handle this case, we maintain, for each (maximal) connected component $C$ that exists at a given time, a subset $X(C)$ of vertices. We will charge to the vertices of $X(C_i)$ in this case. The sets $X$ are defined inductively as described in the pseudocode of the charging scheme below. As we prove below, each vertex is charged by this type of charging only once, we the size of the sets $X$ is large enough to compensate for the cost of recoloring.

Note that these cases are exhaustive as $C_i$ and $C_i^{\prime }$ cannot be both large and heavy, otherwise the edge would not have been input to the simulation $A$. The following summarizes in a formal manner the charging scheme described above. We then formally prove the desired properties of the charging scheme as stated informally above.
Charging scheme $\mathrm{■}$ Initially, $X\left(\left\{v\right\}\right)=\left\{v\right\}$ for every vertex $v$. $\mathrm{■}$ When a new edge $e_i=(u_i,v_i)$ arrives connecting components $C_i$ and $C_i^{\prime }$: 1. Suppose $𝒜$ recolors $C_i$ (a) Charge vertices as follows: i. If $C_i$ is small, then charge $1$ to each vertex in $C_i$ ii. If $C_i$ is large and light, then charge $1$ to each vertex in $C_i\setminus R_{i-1}$, i.e., the vertices of $C_i$ that were never recolored before step $i$. iii. If $C_i$ is large and heavy, $C_i^{\prime }$ small and heavy, then charge $1$ to each vertex in $R_{i-1}\left(C_i^{\prime }\right)$ iv. If $C_i$ is large and heavy, $C_i^{\prime }$ light, then charge $1$ to each vertex in $X\left(C_i\right)$. (b) If $C_i^{\prime }$ is light, then $X\left(C_i\cup C_i^{\prime }\right)=\left(C_i\cup C_i^{\prime }\right)\setminus R_i$; else $X\left(C_i\cup C_i^{\prime }\right)=X\left(C_i\right)\cup X\left(C_i^{\prime }\right)$ 2. If $𝒜$ does not recolor, then $X\left(C_i\cup C_i^{\prime }\right)=X\left(C_i\right)\cup X\left(C_i^{\prime }\right)$

Observe that every vertex charged is either in $C_i$, the component being recolored, or was previously recolored (case 1(a)iii). Thus every vertex that is charged is in $R$. It now remains to show that in each step, the number of vertices being charged is at least a constant fraction of the number of vertices being recolored – i.e. the total charge received by the vertices can pay for the recoloring cost – and that each vertex is not charged more than $O(\log D)$ times.

We prove this claim by induction on $|C|$, the base case being $|C|=1$. By definition for $C$, such that $|C|=1$, $X(C)=C$ and hence the claim hold, since . For the inductive step, suppose that $C=A\cup A^{\prime }$, and that $|X(A)|\ge |A|(1-\alpha )/5$ and $|X(A^{\prime })|\ge |A^{\prime }|(1-\alpha )/5$. If $X(C)=X(A)\cup X(A^{\prime })$ (which occurs in two distinct cases in the specifications of the charging scheme) then, since $A\cap A^{\prime }=\mathrm{\varnothing }$,

Otherwise, $X(C)=(A\cup A^{\prime })\setminus R_i$. Then, when $e_i$ arrived, $𝒜$ recolored one of the two connected components $A,A^{\prime }$ and the other connected component was light. Suppose w.l.o.g. that $𝒜$ recolored $A$, and $A^{\prime }$ was light. Then, we have

By the lightness of $A^{\prime }$, we have that $|A^{\prime }\setminus R_{i-1}|\ge |A^{\prime }|(1-\alpha )\ge |C|(1-\alpha )/5$ by Lemma 16. This concludes the induction argument. $\mathrm{⊲}$

We show that the number of vertices being charged is at least $|C|(1-\alpha )/20$ in every case. In case 1(a)i, we charge $C$ so this clearly holds. In case 1(a)ii, lightness of $C$ implies that $|C\setminus R_{i-1}|\ge |C|(1-\alpha )/5\ge |C|(1-\alpha )/20$. In case 1(a)iii, we have $|R_{i-1}(C^{\prime })|\ge |C^{\prime }|(1-\alpha )/5\ge |C|(1-\alpha )/20$ where the first inequality is due to $C^{\prime }$ being heavy and the second due to Lemma 16. For case 1(a)iv, we get that $|X(C)|\ge |C|(1-\alpha )/5$ from Claim 18. $\mathrm{⊲}$

By Lemma 16, the number of times a vertex $v$ is charged due to case 1(a)i is $O(\log D)$. The number of times a vertex $v$ is charged due to line 1(a)ii is at most once since it is recolored and now belongs to $R_i$. The number of times it can be charged due to 1(a)iii is at most once since it now belongs to a large component. The number of times it can be charged due to 1(a)iv is at most once since afterwards it belongs to $R_i$ and thus cannot be in $X(A)$ for any future component, due to the way the set $X$ is modified in 1b. $\mathrm{⊲}$

Combining the fact that only vertices in $R$ can be charged and Claims 19 and 20, we are done proving Lemma 17. $◀$

We are now ready to conclude the analysis of Algorithm $ℬ$.

By Lemma 14, the total cost incurred by recoloring using a special color is $O(|R|\cdot \frac{{\beta }^2}{\alpha })$. Next, note that by the code the sequence given as input to $𝒜$, ${\sigma }^{\mathrm{sim}}$, is $(D,\alpha )$-moderate. It therefore follows from Lemma 17 that the total cost due to the simulation of $𝒜$ is $O(|R|\log D/(1-\alpha ))$. Since by Lemma 15 the optimal cost is $\mathrm{\Omega }(|R|)$, we are done by picking, say, $\alpha =1/2$. $◀$

At any time $t\ge i$, if at the beginning of time step $t$, $\mathrm{level}(u)\ne \mathrm{level}(v)$, we are done as the levels do not change (step 5(a)). If at the beginning of time step $t$ $\mathrm{level}(u)=\mathrm{level}(v)=k$ and ${\sigma }^k\circ e_i$ is moderate then $e_i$ is added ${\sigma }^k$ (step 5(c)), and the claim holds. In the remaining case (Step 5(d)), $u$ is promoted and $v$ is not, hence their level will not be the same at the end of time step $t$. $\mathrm{⊲}$

The correctness of the algorithm is now straightforward.

Follows from the fact that at any time (1) two vertices of different levels are not colored by the same color, (2) if an edge $e=(u,v)$ exists and $\mathrm{level}(u)=\mathrm{level}(v)=k$, then $e\in {\sigma }^k$ (3) the correctness of ${𝒜}_k$ for all $k$. $◀$

We now proceed to give an upper bound on the cost paid by Algorithm $𝒞$ and on the number of colors it uses. Recoloring occurs in $𝒞$ either by some ${𝒜}_j$ or by procedure promote (which recolors to the initial color of the corresponding level). We analyze each separately.

Let us denote by ${\mathrm{OPT}}_2(\sigma )$ the optimal cost of recoloring an input sequence $\sigma$, when only the two initial colors of unit cost are available; the initial coloring of the vertices is understood from the context. Regarding recoloring by some ${𝒜}_j$, we have the following. Let $R_j$ denote the set of vertices whose color was altered by ${𝒜}_j$.

Follows from Lemma 17 and the fact that ${\sigma }^j$ is $(\tau ,\alpha )$-moderate by construction. $◀$

We note that the recoloring done by the algorithm are either (1) changes of $c^k(v)$, for $v$ such that $\mathrm{level}(v)=k$, done by $A_k$, or (2) change of the color of $v$ due to the change of $\mathrm{level}(v)$, in procedure promote. We now analyze the cost due to the latter; the former was analyzed in the above lemma.

We use the following definition.

Clearly, the total cost due to recoloring by promote is at most ${\sum }_j|F_j|$, because each excess edge causes at most one vertex to be recolored (indirectly) when promote changes the level of a vertex. Then by Lemma 13 we have:

We now have that the total cost of the algorithm is

Next, we bound ${\sum }_{j\ge 1}|R_j|$. We will need the following lemma.

Let $S_j$ be the set of vertices $u$ to which $\text{promote}(u,j)$ was applied at some point in the algorithm. Clearly, $|S_j|=|F_{j-1}|$, because each $(j-1)$-excess edge promotes a single vertex to level $j$. It follows that $|S_j|=|F_{j-1}|\le \beta \cdot \frac{|R_{j-1}|}{\alpha \tau }$ by Lemma 25. Now, $E^j\subseteq G[S_j]$, because an edge is appended to ${\sigma }^j$ only if both its endpoints are in $V^j$ at that time. Since $E^j$ is a subset of the edges of a graph with largest bond size $\beta$, we have from Corollary 11 that $|E^j|\le \beta (|S_j|-1)$. We therefore conclude that $|E^j|\le {\beta }^2\cdot \frac{|R_{j-1}|}{\alpha \tau }$. $◀$

We can now prove that $|R_j|$ decreases exponentially with $j$, for large enough $\tau$.

Since ${𝒜}_j$ recolors a vertex only if it is incident on an input edge, we have that $|R_j|\le 2|E^j|$. The result follows from Lemma 26. $◀$

Proposition 27 immediately gives an upper bound on the number of colors used by Algorithm $𝒞$.

Let $\gamma =\frac{2{\beta }^2}{\alpha \tau }$. By Step d of Algorithm $𝒞$, . Clearly, $|R_1|\le n$, and hence, by Proposition 27 we have that $|R_j|\le n\cdot {\gamma }^j$. Hence, for $j>{\log }_{(1/\gamma )}n$ we have that . The result follows, since $\log (1/\gamma )=\log \tau -O(\log \beta )=\mathrm{\Theta }(1/ϵ)$. $◀$

We can now conclude the analysis of Algorithm $𝒞$.

Fix $\alpha =1/2$. The number of colors is given by Corollary 28. By Inequality (1), the total cost of the algorithm is at most

Since $ϵ>\frac{1}{2\log \beta +3}$ and $\alpha =1/2$, we get that $\tau =2^{1/ϵ}$ and so $\frac{\beta }{\alpha \tau }+\frac{\log \tau }{1-\alpha }\le O(1/ϵ)$. Moreover, Proposition 27 implies that ${\sum }_{j\ge 1}|R_j|\le O(1)|R_1|$. By Lemma 15, we have that $|R_1|\le O(1){\mathrm{OPT}}_2({\sigma }^1)\le O(1){\mathrm{OPT}}_2(\sigma )$. Thus, ${\sum }_{j\ge 1}|R_j|\le O(1){\mathrm{OPT}}_2(\sigma )$. Therefore, the total cost of the algorithm is at most $O(1/ϵ){\mathrm{OPT}}_2(\sigma )$, as desired. $◀$