16.2.2. Cluster Editing

As a second example of a simple FPT branching algorithm, let us consider the cluster editing problem. We obtain a cluster graph \(G^*\) from the original graph \(G\) by deciding for each edge in \(G\) whether to keep it or remove it and for each edge not in \(G\) whether to add it or leave it out. However, this leaves \(\binom{n}{2}\) edges to be considered while the number of required edits \(k\) is hopefully much smaller. Here we discuss a simple \(O^*\bigl(3^k\bigr)\)-time algorithm.

The key observation is this: If there are three vertices \(u, v, w\) such that the edges \((u, v)\) and \((v, w)\) belong to \(G\) but the edge \((u, w)\) does not, then at least one edit is required that adds or removes one of these three edges in order to obtain a cluster graph \(G^*\) from \(G\). Indeed, if both the edges \((u, v)\) and \((v, w)\) belong to \(G^*\), that is, we remove neither of these two edges, then \(u\) and \(w\) belong to the same connected component of \(G^*\), so the edge \((u, w)\) must be in \(G^*\) and thus must be added. This suggests the following branching algorithm \FuncSty{CE} to decide whether a given cluster edit instance \((G, k)\) is a yes-instance and, if so, return a minimum cluster edit set for \(G\):

\(\boldsymbol{\textbf{CE}(G, k)}\):

• If \(k < 0\), then there is no cluster graph \(G^*\) obtainable from \(G\) using at most \(k\) edge edits, so \((G, k)\) is a no-instance and we return "No".

• If \(k \ge 0\) and every connected component in \(G\) is a clique, then no edge edits are needed to turn \(G\) into a cluster graph. Thus, \((G,k)\) is a yes-instance and \(M = \emptyset\) is an optimal set of edge edits, which we return.

• If \(k \ge 0\) and there exists a connected component of \(G\) that is not a clique, then this component contains three vertices \(u, v, w\) such that \((u, v), (v, w) \in E\) and \((u, w) \notin E\). (The proof of this fact is left as Exercise 16.1.) In this case, we make three recursive calls \(\boldsymbol{\textbf{CE}(G_{u,v}, k-1)}\), \(\boldsymbol{\textbf{CE}(G_{v,w}, k-1)}\), and \(\boldsymbol{\textbf{CE}(G_{u,w}, k-1)}\), where \(G_{u,v}\) is obtained from \(G\) by removing the edge \((u, v)\), \(G_{v,w}\) is obtained by removing the edge \((v, w)\), and \(G_{u,w}\) is obtained by adding the edge \((u, w)\).

  • If all three recursive calls return "No!, then we return "No".

  • If the recursive call \(\boldsymbol{\textbf{CE}(G_{u,v}, k-1)}\) returns a minimum cluster edit set \(M_{u,v}\) for \(G_{u,v}\) and the other two recursive calls return "No" or cluster edit sets that are no smaller than \(M_{u,v}\), then return \(M_{u,v} \cup \{\boldsymbol{\textbf{Delete}(u,v)}\}\).

  • If the recursive call \(\boldsymbol{\textbf{CE}(G_{v,w}, k-1)}\) returns a minimum cluster edit set \(M_{v,w}\) for \(G_{v,w}\) and the other two recursive calls return "No" or cluster edit sets \(M_{u,v}\) and \(M_{u,w}\) such that \(|M_{u,v}| > |M_{v,w}|\) and \(|M_{u,w}| \ge |M_{v,w}|\), then return \(M_{v,w} \cup \{\boldsymbol{\textbf{Delete}(v,w)}\}\).

  • If the recursive call \(\boldsymbol{\textbf{CE}(G_{u,w}, k-1)}\) returns a minimum cluster edit set \(M_{u,w}\) for \(G_{u,w}\) and the other two recursive calls return "No" or cluster edit sets that are strictly larger than \(M_{u,w}\), then return \(M_{u,w} \cup \{\boldsymbol{\textbf{Add}(v,w)}\}\).

Exercise 16.1: Any graph with at most two vertices is a cluster graph. Prove that any graph \(G\) with at least three vertices is a cluster graph if and only if \(G[W]\) is a cluster graph for every subset of vertices \(W \subseteq V\) with \(|W| = 3\). Conclude that this implies that if \(G\) is not a cluster graph, then there must exist three vertices \(u, v, w\) in \(G\) such that \(G\) contains the two edges \((u,v)\) and \((v,w)\) but not the edge \((u,w)\).

Since this algorithm has the branching vector \((1, 1, 1)\), it clearly has running time \(O^*\bigl(3^k\bigr)\). The next lemma shows that it is correct.

Lemma 16.6: If \(G\) has three vertices \(u, v, w\) such that \((u, v), (v, w) \in E\) and \((u, w) \notin E\), then \((G, k)\) is a yes-instance of the cluster editing problem if and only if one of the instance \((G_{u,v}, k-1)\), \((G_{v,w}, k-1)\), and \((G_{u,w}, k-1)\) is a yes-instance. Moreover, if \(M_{u,v}\), \(M_{v,w}\), and \(M_{u,w}\) are minimum cluster edit sets for \(G_{u,v}\), \(G_{v,w}\), and \(G_{u,w}\), respectively, then the smallest of \(M_{u,v} \cup \{\boldsymbol{\textbf{Delete}(u,v)}\}\), \(M_{v,w} \cup \{\boldsymbol{\textbf{Delete}(v,w)}\}\), and \(M_{u,w} \cup \{\boldsymbol{\textbf{Add}(u,w)}\}\) is a minimum cluster edit set for \(G\).

Proof: Let \(M\), \(M_{u,v}\), \(M_{v,w}\), and \(M_{u,w}\) be minimum cluster edit sets for \(G\), \(G_{u,v}\), \(G_{v,w}\), and \(G_{u,w}\), respectively. Then

\begin{align} |M| &\le \min \begin{pmatrix} |M_{u,v} \cup \{\boldsymbol{\textbf{Delete}(u,v)}\}|\\ |M_{v,w} \cup \{\boldsymbol{\textbf{Delete}(v,w)}\}|\\ |M_{u,w} \cup \{\boldsymbol{\textbf{Add}(u,w)}\}| \end{pmatrix}\\ &= \min(|M_{u,v}|, |M_{v,w}|, |M_{u,w}|) + 1\tag{16.1} \end{align}

because each of the sets \(M_{u,v} \cup \{\boldsymbol{\textbf{Delete}(u,v)}\}\), \(M_{v,w} \cup \{\boldsymbol{\textbf{Delete}(v,w)}\}\), and \(M_{u,w} \cup \{\boldsymbol{\textbf{Add}(u,w)}\}\) is a cluster edit set for \(G\). Conversely, since \((u,v), (v,w) \in G\) and \((u,w) \notin G\), we have \(\boldsymbol{\textbf{Delete}(u,v)} \in M\), \(\boldsymbol{\textbf{Delete}(v,w)} \in M\) or \(\boldsymbol{\textbf{Add}(u,w)} \in M\). W.l.o.g., assume that \(\boldsymbol{\textbf{Delete}(u,v)} \in M\). Then \(M \setminus \{\boldsymbol{\textbf{Delete}(u,v)}\}\) is a cluster edit set for \(G_{u,v}\). Thus,

\[\begin{aligned} \min(|M_{u,v}|, |M_{v,w}|, |M_{u,w}|) &\le |M_{u,v}|\\ &\le |M \setminus \{\boldsymbol{\textbf{Delete}(u,v)}\}|\\ &= |M| - 1. \end{aligned}\tag{16.2}\]

Together, (16.1) and (16.2) show that \(|M| = \min(|M_{u,v}|, |M_{v,w}|, |M_{u,w}|) + 1\). Thus, \((G,k)\) is a yes-instance if and only if \((G_{u,v}, k-1)\), \((G_{v,w}, k-1)\) or \((G_{u,w}, k-1)\) is a yes-instance.

The smallest edit set among \(M_{u,v} \cup \{\boldsymbol{\textbf{Delete}(u,v)}\}\), \(M_{v,w} \cup \{\boldsymbol{\textbf{Delete}(v,w)}\}\), and \(M_{u,w} \cup \{\boldsymbol{\textbf{Delete}(u,w)}\}\) has size \(\min(|M_{u,v}|, |M_{v,w}|, |M_{u,w}|) + 1 = |M|\). Since all three sets are cluster edit sets for \(G\), the smallest of these three sets is a minimum cluster edit set for \(G\). ▨