Static to Dynamic Correlation Clustering

The first (large) constant approximation algorithm is due to [6]. The constant was then improved to $4$ by [18] who also proved that the problem is APX-hard. Later, Ailon, Charikar, and Newman [2] introduced the crucial idea of pivot-based algorithms, where in each round, the algorithm picks a random unclustered vertex and creates a new cluster consisting of this vertex and some of its neighbors. They gave a combinatorial 3-approximation algorithm and improved the approximation ratio to 2.5 by rounding a standard linear program (LP) which has an integrality gap of at least 2. [19] improved the approximation ratio to 2.06 using a more sophisticated rounding scheme of the same LP.

To bypass the integrality gap of 2, Cohen-Addad, Lee, and Newman [23] used the Sherali-Adams hierarchy and achieved a $1.995$-approximation, which was then improved to a $1.73$-approximation by combining the pivot-based rounding with the newly-developed set-based rounding [22]. The best approximation algorithm currently known is a ${1.485}^{\text{<a href="\#footnotex1" title="Footnote 1 ‣ Static to Dynamic Correlation Clustering" class="ltx\_ref ltx\_font\_italic" style="font-size:70\%;"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}}$-approximation due to [15] which proposed the Cluster LP to achieve this result. They also showed that obtaining a 25/24-approximation is NP-hard.

When it comes to deterministic algorithms, the fastest one with (large) constant factor approximation is Algorithm 1 in [21] which has a trivial deterministic implementation is $O(nm)$ time. A deterministic factor $(3+\epsilon )$- approximation is presented in [26] running in $\tilde{O}(n^3)$ time. One can obtain a deterministic 2.5-approximation in (large) polynomial time by first solving the $O(n^3)$-sized LP with the Ellipsoid method and rounding it with the work of [30]. ²²2In the conference version of [12, Proposition 2.1], the authors claim that the existence proof of [5] gives a deterministic $O(m)$ time constant-approximate algorithm. The authors have since retracted their claim in the most recent arXiv version [11].

For the purpose of transforming static algorithms into dynamic ones, our best hope are those with near-linear running time, that is $\tilde{O}(m)$-time, where $m$ is the number of edges. We remark that while sublinear time algorithms exist, their sublinear time holds only when $m=\omega (n)$. As we have to deal with the case $m=O(n)$, these algorithms are not different from those with a near-linear running time for our purpose. The best deterministic running time of $O(nm)$ from [21] is thus far too slow.

Among all near-linear time algorithms, the first one is the classical linear time $3$-approximate Pivot algorithm of [2]. The first sublinear time algorithm in $O(n{\log }^{2}n)$ time with constant approximation ratio is from [5], which is based on the parallel algorithm of [21]. We also have the more recent local-search based $1.847$-approximation of [24] which runs in sublinear time. Recently, in [13], it was shown that the $1.485$-approximation algorithm based on the Cluster LP from [15] can be implemented in sublinear time. All of these near-linear time algorithms are Monte Carlo algorithms.

The dynamic setting has also been explored. Much of the work here has been on how to maintain a pivot-based clustering under these changes. One result is that of [8], which shows how to maintain a Maximal Independent Set with an update time of $O({\log }^{2}n{\log }^2\mathrm{\Delta })$ where $\mathrm{\Delta }$ is the maximum degree of any vertex. This can be used to maintain the $3$-approximate Pivot algorithm for a fixed permutation of pivots. This was since improved in [25] to maintaining a $(3+\epsilon )$-approximation with an update time of $O(1/\epsilon )$. Finally, it has recently been shown that the barrier of $3$-approximation indeed can be broken in the dynamic setting in [7]. Here they give a $2.997$-approximation algorithm, again based on maintaining the pivot under additions and deletions with a polylogarithmic update time. All of these pivot-based results only work with an oblivious adversary: they fix the random order of the pivots in advance, maintaining it for all updates. All of these results only work with an oblivious adversary: they fix the random order of the pivots in advance, maintaining it for all updates.

For all the above pivot-based dynamic algorithms, an adaptive adversary could easily learn the order of the pivots, and then make them perform very badly afterward by constructing an input graph that is bad for this pivot order. Recently, [12] presented a dynamic large constant factor approximation algorithm supporting updates in $O({\log }^{2}n)$ amortized time against an adaptive adversary. It is based on the non-pivot-based $O(n{\log }^{2}n)$ time randomized algorithm from [5], but at the cost of a large approximation factor. They also mention “It is unclear how the pivot-based algorithms could be made to work in the adversarially robust setting”[12, 2nd page]. In particular, this concerns the classic 3-approximate Pivot algorithms.

The general issue of getting a Monte Carlo randomized dynamic algorithm to work against an adaptive adversary is addressed in [9]. They show a generic transformation from the oblivious setting to the adaptive setting using tools from differential privacy, but the transformation has an extra polynomial factor on the update time even in the few cases studied in their paper. In this paper, however, we are aiming for update times that are polylogarithmic or even constant.

A recent result from [4] shows that for a fully-dynamic graph, we can maintain a linear sketch of sublinear $\tilde{O}(n)$ size from which we can derive a correlation clustering in randomized polynomial time. The basic idea is that they desparsify the sketch into a graph $G^{\prime }$ that is similar to the current graph $G$ in the sense that any correlation clustering will have almost the same cost in $G$ and $G^{\prime }$. They can therefore apply any polynomial time correlation clustering algorithm to $G^{\prime }$ and get an almost as good correlation clustering for $G$. This result follows the streaming tradition and is very interesting from an information theoretic perspective. However, spending polynomial time whenever we want a clustering of the current graph is not good from our perspective of dynamic graph algorithms, where we want to maintain a concrete clustering in constant or logarithmic time per edge update.

The interesting aspect from [4] is that their sketch is of $\tilde{O}(n)$ size. A fundamental issue from a fully-dynamic perspective is that a randomized sketch of sublinear size appears to sacrifice the ability to handle a non-oblivious adaptive adversary. The issue is that if we use a randomized sketch of the current graph, and if we after each update reveal a clustering based on the random choices in the sketch, then the adversary can learn about these random choices and then make updates that destroy the quality of the sketch. This is not so much an issue for the streaming scenario in [4] where they just maintain the sketch, and only in the end construct the clustering in polynomial time. However, it is a major issue if we want to maintain a clustering throughout the updates against an adaptive adversary, and this is the setting we are considering in this paper.

We will now be more precise about how we want to represent a graph $G=(V,E)$. Instead of storing the edges $E$, we will store a clustering $𝒞$ together with the set $D$ of violated pairs, that is, unordered vertex pairs $(u,v)$ such that either $(u,v)\in E$ but $u$ and $v$ are in different clusters in $𝒞$, or $(u,v)\notin E$ but $u$ and $v$ are in the same cluster in $𝒞$. The correlation clustering cost of $𝒞$ is exactly $|D|$. We shall refer to set $D$ as the violation of the clustering $𝒞$, and to $(𝒞,D)$ as the cluster representation, noting that it uniquely defines the edge set $E$. We say that the cluster representation $(𝒞,D)$ is $c$-approximate if the clustering is $c$-approximate, that is, if $|D|$ is at most $c$ times the minimum correlation clustering cost. In addition, it is simple to reconstruct $E$ from $(𝒞,D)$.

We can think of the cluster representation as a graph compression: It is never worse than the actual graph representation by more than the $O(n)$ space required to store $𝒞$, since we can always choose the clustering to be a singleton cluster for each vertex. Then $D$ is just the set $E$ of edges in the graph. In the other extreme, if we have all vertices forming a single cluster, then the violation $D$ is exactly the set of non-edges $\left(\genfrac{}{}{0pt}{}{V}{2}\right)\setminus E$. However, our representation could be much better in both of these extremes if the clustering $𝒞$ has small cost. We can in fact bound the space required by $O(n+|D|)$, from which we get these properties. It is worth mentioning that one can ensure $O(n)$ additional space compared to the normal graph representation, with two global counters on the size of $D$ and $E$. However, this is not necessary to achieve our main results.

To get a fully dynamic correlation clustering algorithm, assume that we have a static algorithm that takes as input an arbitrary cluster representation $(𝒞,D)$ and outputs a $c$-approximate cluster representation $({𝒞}^{\prime },D^{\prime })$ in $O(t|D|)$ time for some parameter $t$. Since $D$ may be much smaller than the edge set $E$, we can think of using $(𝒞,D)$ as a warm start. We also note that $|D|$ might be much smaller than the clustering $𝒞$, which is of size $\mathrm{\Theta }(n)$. Therefore, the static algorithm can only produce a clustering ${𝒞}^{\prime }$ with limited modification of the input clustering $𝒞$.

Now, in correlation clustering, each edge update will only change the cost of a given clustering by $1$. Thus, if at some point, we have a good clustering $𝒞$ with violation $D$, then the same clustering will remain good for $O(\epsilon |D|)$ edge updates. More precisely, we will show that if $𝒞$ was a $c$-approximation, then $𝒞$ will remain a $(1+\epsilon )c$-approximation after $\mu |D|$ edge updates, where $\mu \le \frac{\epsilon }{2(1+\epsilon )c}$. Therefore, it suffices to reconstruct a new $c$-approximate clustering after $\mu |D|$ edge updates.

In the period between reconstructions, we will just store the sequence $U$ of $\mu |D|$ edge updates (so the violation is not updated explicitly as that would involve hashing). For a fixed clustering $𝒞$, we will show how to update our violation $D$ according to the edge updates in $U$ deterministically in $O(|D|+|U|)=O(|D|)$ time. Next, we apply the assumed static algorithm to our updated cluster representation $(𝒞,D)$ to reconstruct a new $c$-approximate cluster representation $({𝒞}^{\prime },D^{\prime })$ in $O(t|D|)$ time. The new clustering ${𝒞}^{\prime }$ will again remain good for the next $\mu |D^{\prime }|$ edge updates.

The result is a $(1+\epsilon )c$-approximate fully-dynamic algorithm with $O(t/\mu )$ amortized update time. With standard background rebuilding, we can de-amortize and get $O(t/\mu )$ worst-case update time. Summing up, we will show:

The above approach works perfectly if our algorithm for the static case is deterministic, but all the known near-linear time static constant approximate algorithms are Monte Carlo algorithms. They only produce a $c$-approximations in expectation or with some error probability bounded by .

Naively, the above should be fine, even against an adaptive adversary, because our current clustering is good if the last rebuild was a $c$-approximation as in the deterministic case, and this happened with probability at least $1-p$. The next rebuild is done using its own independent randomness, so an adaptive adversary cannot do anything to break a guarantee that holds for any input cluster representation, e.g., that it is a $c$-approximation with probability at least $1-p$. Nevertheless, there is an issue since the new cluster representation $({𝒞}^{\prime },D^{\prime })$ will be kept for $\mu |D^{\prime }|$ updates. Hence, if it is bad in the sense that $D^{\prime }$ is large, then it will survive for longer time. We will present a concrete example about this effect, showing that we get a logarithmic factor more chances of failing at a particular update. In fact, this does not even depend on the adversary being adaptive. The same construction can be done by an oblivious adversary.

It is a bit subtle what we mean by saying that the dynamic algorithm is correct with some probability against an adaptive adversary, since this adversary knows our current clustering and can see exactly how bad it is compared with the optimum. It is therefore never a probabilistic statement whether the current clustering is good to the adversary. However, we can study statements of this kind: for any given update step $i$, what is the probability $P_i$ that we have a bad clustering just after update $i$. An adaptive adversary (1) can choose $i$ in advance, (2) knows our current clustering at any time, and (3) can adaptively pick the first $i$ updates so as to maximize $P_i$. Yet we want to bound $P_i$.

The above definition of $P_i$ may seem a bit cryptic, but this is important when we want constant error probability with constant update time. More specifically, with a long update sequence, we can create and remove a linear number of different constant sized graphs. Our dynamic algorithm will cluster all of them independently, so if it fails with constant probability, then we expect it to fail on a constant fraction of them, and the adaptive adversary will see when it fails. Nevertheless we promise that it is correct just after a predetermined update $i$ with constant probability $P_i$. If we increase the update time to $O(\log n)$, then we can make the error probability so small that we do not expect any errors over a polynomially long update sequence, and then we do not need the special definition of $P_i$.

What we first show is that if the static algorithm gives a $c$-approximation with probability at least $1-p$, then our fully dynamic algorithm gives an $(1+\epsilon )c$-approximation with error probability $P_i=O(p\log n)$.

We can avoid losing the factor $\log n$ if the static algorithm for input clustering $(𝒞,D)$, $|D|\ge 1$, produces a $c$-approximation with probability at least $1-q(|D|)$ where $q$ falls at least inversely in $|D|$. Then $P_i$ is bounded by $O(q(1))$.

Technically, the assumption of $|D|\ge 1$ means that we avoid dividing by $0$. However, if our input cluster representation had $|D|=0$, then it would be a zero-cost optimal solution, and then we would not involve the static algorithm to try computing a better solution.

Finally, we have a combined result. Suppose the static algorithm for input clustering $(𝒞,D)$, $|D|\ge 1$ produces a $c$-approximation with probability at least $1-p$ and an $O(c)$ approximation with probability at least $1-q(|D|)$ where again $q$ falls at least inversely in $|D|$. Then $P_i$ is bounded by $O(p+q(1))$.

We shall see how all these bounds play together with existing static algorithms, but first we summarize them in the theorem below. In this theorem, we consider randomized Monte-Carlo algorithms that aim at certain targets that they may fail to achieve.

By combining the two cases above, we can get a best of both worlds statement, namely that we can get the approximation ratio of Theorem 3(a) case while avoiding the logarithmic blow-up in the probability, by using the properties of Theorem 3(b).

It should be mentioned that while this theorem does give results against an adaptive adversary, this does not mean that it can be strengthened against an oblivious adversary. We are in fact later going to show a matching lower bound for the probability of failure, which contains a strategy that can be implemented both by an adaptive and an oblivious adversary.

It is also worth noting that the probability $P_i$ in the statement is not independent for different values of $i$. You only get independence between two updates $i$ and $j$ if between processing them the clustering is rebuild. The frequency of this is however dependent on the cost of the clustering, a value that is very easy to influence by the adversary.

One may wonder if one could get the error probabilities to work simultaneously for a sequence of $T$ updates without resorting to a union bound, multiplying the error probability by $T$. As a base state, consider an arbitrarily large graph consisting of disjoint cliques, including singleton vertices. The optimal correlation clustering cost is zero, so any approximation algorithm has to agree on the clustering into cliques. With $s$ updates, the adversary can create a nontrivial instance of correlation clustering over some of the vertices. And with $s$ more updates, the adversary can change the graph back to the base state. Therefore, starting from the base state, in $T$ updates, the adversary can create $T/(2s)$ nontrivial and independent instances to challenge the algorithm, so getting global error bound better than a union bound is not likely.

Our result will be improved if there exists a deterministic $O(|D|)$ time algorithm $\widehat{𝒜}$ with constant approximation ratio. According to Theorem 2, this would give a deterministic dynamic algorithm that maintains a clustering of $(1+\epsilon )c$ approximation at every update. In addition, the existence would also imply that the dynamic algorithm would inherit any expected approximation ratio from algorithm $𝒜$, instead of only achieving this approximation ratio with constant probability, since we can get a deterministic upper bound on the cost anytime we rebuild the clustering. This would also give a worst-case guarantee on the quality of the clustering even when $𝒜$ always fails.

We will now discuss how the known near-linear static algorithms can be modified and used in our dynamic framework.

First, as a general standard note. Suppose we have a Monte-Carlo algorithm that, given a cluster representation $(𝒞,D)$, aims to produce a $c$-approximate cluster representation $({𝒞}^{\prime },D^{\prime })$ and fails with probability at most $p$. We switch to the new clustering ${𝒞}^{\prime }$ only if it has lower cost, that is, if . This means that if we make $k$ iterations of the algorithm, then the probability that we do not end up with a $c$-approximation drops to $p^k$.

The first algorithm we consider is the classical 3-approximate Pivot algorithm from [2]. It takes $O(m)$ time on a given graph, and we show how to implement it in $O(|D|)$ time for a given input clustering $(𝒞,D)$. This ends up requiring weighted sampling of vertices instead of the normal uniform one. In addition, this also has the consequence of showing how we can speed up the running time of the Pivot algorithm with a “hot start”. The approximation factor of the Pivot algorithm is in expectation, but making $O(\log \log n)$ iterations, we get a $(3+o(1))$-approximation with failure probability $o(1/\log n)$. Thus, we have:

Plugging Theorem 6 into Theorem 3(a) using a sufficiently small $\epsilon >0$, we get:

The main advantage of Corollary 7 over the previous pivot-based dynamic algorithms with approximation factors around 3 is that it works against an adaptive adversary. Compared to [12], by setting $\delta =1/\mathrm{poly}(n)$, Corollary 7 improves both the approximation ratio from a large constant to $3+ϵ$ and the update time from amortized $O({\log }^{2}n)$ to worst-case $O(\log n)$, with the same error probability.

Next, we consider the 1.847-approximate local search algorithm from [24]. As discussed earlier, it uses $\mathrm{\Omega }(n\log n)$ time even if we just want constant error probability, but this is not $O(m)$ time if $m=o(n\log n)$. In this paper, we show an $O(m)$ time implementation of the local search algorithm with exponentially small error probability of $\exp (-\sqrt{m}/{\log }^{3}m)$. The previous static algorithm tries to find clusters with roughly the same probability regardless of their sizes. However, we notice that each small cluster only has a small random contribution to the total cost, so their total contribution is strongly concentrated and we do not need to find all of them. On the other hand, for large clusters, we can afford to spend more time and make sure to find all of them with high probability. Our full implementation is based on a smooth sampling distribution according to the cluster sizes. Moreover, our implementation can also be made efficient in cluster representation, as stated below.

The next corollary follows from this special case of Theorem 8 when $𝒞$ is the set of singletons and $D=E$.

Since the error probability in Theorem 8 falls more than inversely in $|D|$, we can apply Theorem 3(b). The approximation factor 1.847 in Theorem 8 is already rounded up by a small constant, so using a sufficiently small $\epsilon >0$ in Theorem 3, we get:

Finally, we want to apply our dynamic framework to the current best 1.485-approximation algorithm from [15] which was implemented in sublinear time in [13]. We will need all the techniques mentioned above. The algorithm has two parts. First it solves the Cluster LP from [15], second it rounds the solution.

The first part aims for a fractional solution to the Cluster LP that is $(1+\epsilon )$-approximate relative to the optimal integral solution. This part uses multiplicative weight updates and finds a nearly optimal fractional solution to the aggregated constraint with the above local search. We face a situation parallel to the one we faced with the local search from [24]. The algorithm is sublinear but not linear if $m=o(n\log n)$ and it only works with constant probability. Using the techniques we used to make the local search from [24] work for Theorem 8, we can take any cluster representation $(𝒞,D)$ and solve the Cluster LP in $O(|D|)$ time, yielding a fractional solution that is $(1+\epsilon )$-approximate relative to the optimal integral solution with probability at least $1-\exp (-\sqrt{|D|}/{\log }^3|D|)$.

In [15, 13], the fractional solution is rounded using pivot-techniques. The rounding gets a 1.485-approximate solution with constant probability. Given a cluster representation $(𝒞,D)$, we want to implement the rounding in $O(|D|)$. Here we can employ some of the techniques we used for the classical 3-approximate pivot in Theorem 6. However, all the rounding algorithms only work with constant failure probability.

The next corollary follows from this special case of Theorem 11 when $𝒞$ is the set of singletons and $D=E$.

Because of the constant error probability from the rounding, we do not currently benefit from the exponentially low error probability for finding the fractional solution. However, it will be important if we one day find rounding algorithms working with higher probability.

We will now plug both Theorem 8 and Theorem 11 into Theorem 4. More precisely, we use Theorem 8 to get an $O(1)$-approximate solution with exponentially high probability, and Theorem 11 to get a below 1.485-approximate cluster representation with constant probability. Applying Theorem 4 with a sufficiently small $\epsilon >0$, we get our main result in Theorem 1.

We will now prove Theorem 3, analyzing how the failure probability of the static algorithm affects the failure probability of the dynamic algorithm.

We are going to consider any update $i^{\ast }$, and we want to bound the probability that our current clustering $𝒦$ is not $(1+\epsilon )c$-approximate when we get to this update. In particular, this requires that the last rebuilt cluster representation $({𝒞}^{\prime },D^{\prime })$ was not $c$-approximate.

Taking a step back, suppose we want to do a rebuild before some update $i$ and the input for this rebuild is the cluster representation $(𝒞,D)$. We then get a new cluster representation $({𝒞}^{\prime },D^{\prime })$ with $|D^{\prime }|\le |D|$ which we will keep for $\mu |D^{\prime }|$ updates. We say that a rebuild happening at update $i$ with input $(𝒞,D)$ is risky with respect to $i^{\ast }$ if $i^{\ast }-i\le \mu |D|$, for if we do not get a , then we will not get a better cluster representation before update $i^{\ast }$. Conversely, if it is not risky, then we know we will get another rebuild before we get to update $j$. Thus, if our clustering is not $(1+\epsilon )c$-approximate at update $j$, then some risky rebuild must have failed. We are going to upper bound the probability that any risky rebuild fails. To do this we are going to bound the number of risky rebuilds that can affect a specific update.

We will now prove Theorem 4. In this case we are working with two static algorithms.

• $\mathrm{■}$

  $𝒜$ that is $c$-approximate with probability $p$ and

• $\mathrm{■}$

  $\widehat{𝒜}$ that is $\widehat{c}$-approximate with probability $q(d)$ where $q$ falls inversely with the input violation size $d$.

Every time we do a rebuild, we apply first $\widehat{𝒜}$, followed by $𝒜$. We are furthermore always going to keep the best solution after each application of both algorithms, so the combined algorithm $𝒜\circ \widehat{𝒜}$ gives the best of both worlds (in fact, $𝒜\circ \widehat{𝒜}$ fails to be $\widehat{c}$-approximate with probability at most $p\cdot q(d)$, but we will not exploit that).

We are again going to fix an update $i^{\ast }$ and we want to show that the dynamic algorithm is $(1+\epsilon )c$-approximate at $i^{\ast }$ with probability $O(p+q(1))$. We define $\mu$ small enough that if we have a $c$-approximate clustering with violation size $d$, then it remains $(1+\epsilon )c$-approximate for $\mu d$ updates. We will also define $\mu$ smaller than $1/6$ and $1/(2\widehat{c})$. Picking the minimum of these three options is still a constant. As in the proof for Theorem 3, we say that a rebuild at update $i$ is at risk with respect to update $i^{\ast }$ if we have input cluster representation $(𝒞,D)$ and $i^{\ast }-i\le \mu |D|$. We then apply $\widehat{𝒜}$ producing a cluster representation $(\widehat{𝒞},\widehat{D})$ that will be used as input for $𝒜$. Next, we only say $𝒜$ is at risk with respect to $i^{\ast }$ if $\widehat{𝒞}$ is $\widehat{c}$-approximate and $i^{\ast }-i\le \mu |D^{\ast }|$. We then apply $\widehat{𝒜}$ to $(\widehat{𝒞},\widehat{D})$ producing the final output $({𝒞}^{\prime },D^{\prime })$ of the rebuild with $𝒜\circ \widehat{𝒜}$.

With the above definitions, suppose we get to update $i^{\ast }$ with a clustering that is not $(1+\epsilon )c$-approximate. Let the last rebuild be at update $i$. Then $𝒜\circ \widehat{𝒜}$ must have failed producing a $c$-approximate clustering ${𝒞}^{\prime }$. Moreover, the whole rebuild must have been at risk, for otherwise, there would be another rebuild before update $i^{\ast }$.

If $\widehat{𝒜}$ succeeded, then $𝒜$ must still have been at risk, for otherwise we again conclude that there would be another rebuild before update $j$. Finally, $𝒜$ must have failed producing a $c$-approximate clustering ${𝒞}^{\prime }$.

Recall that $\widehat{𝒜}$ fails producing a $\widehat{c}$-approximate clustering with probability $q(d)$ where $q$ falls inversely with the input violation size $d$. As in our previous analysis, we would like to conclude that the probability that we ever fail a risky application of $\widehat{𝒜}$ which fails is $O(q(1))$. However, we need to revisit the argument to check that we are not cheating because the full rebuild also applies $𝒜$.

Consider a risky rebuild at update $i$. With input violations size $d$, risky means that $i^{\ast }-i\le \mu d$. We will now apply Lemma 15 which doesn’t care how the rebuild is done, so it also applies when now rebuild with $𝒜\circ \widehat{𝒜}$. The lemma states that we can perform at most $3$ rebuilds with input violations above $d/2$ between update $i$ and $i^{\ast }$.

As before, we now define $Q(d)$ as the maximal probability that ${𝒜}^{\ast }$ ever fails on on a risky rebuild starting from input violation size at most $d$. Then $Q(d)\le 3q(d/2)+Q(d/2)=O(q(1)).$ We will now assume that $\widehat{𝒜}$ never fails a risky rebuild. The last rebuild must then have included a risky application of $𝒜$ which failed. We will bound the probability of this event by $O(p)$. For this we use the following lemma.

To swap in a new solution, for each vertex we maintain two entries, the possible ids of clusters that a particular vertex can belong to. These correspond to the clustering the vertex belongs to in the old clustering and the one in the new clustering. We furthermore have a global flag that indicates whether to use the old clustering or the new one. The way we use this information is that if two options exist for the cluster a vertex can belong to, then the global flag decides. Otherwise, the vertex belongs to the only cluster that is written down. This means that we can swap in the new solution by flipping the global flag.

After we have swapped in the new solution, we spend time proportional to the number of updates for the old computation to clean up the vertices that have two cluster ids written down. After that, the new solution has become the old one, so we finally flip the global flag to say use the old solution if it exists, to be ready for the next round of computations.