16.4.1.1. Case 1

In this case, the following lemma shows that it suffices to make only two recursive calls on \((G_{u,v}, k-1)\) and \((G_{v,w}, k-1)\). Thus, the branching vector of the algorithm in this case is \((1, 1)\), resulting in this case having branching number \(2\).

Lemma 16.13: If \(v\) is the only common neighbour of \(u\) and \(w\), then \((G, k)\) is a yes-instance of the cluster editing problem if and only if one of \((G_{u,v}, k-1)\) and \((G_{v,w}, k-1)\) is.

Proof: We already know that \((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. Thus, it suffices to prove that \((G_{u,v}, k-1)\) or \((G_{v,w}, k-1)\) is a yes-instance if \((G_{u, w}, k-1)\) is.

Consider a cluster graph \(G^*\) that can be obtained from \(G_{u,w}\) using at most \(k-1\) edge edits. If \(u\) and \(w\) belong to different components of \(G^*\), then \((u,v) \notin G^*\) or \((v,w) \notin G^*\). Thus, \(G^*\) can be obtained from \(G_{u,v}\) or \(G_{v,w}\) using at most \(k-1\) edge edits, that is \((G_{u,v},k-1)\) or \((G_{v,w},k-1)\) is a yes-instance.

If \(u\) and \(w\) belong to the same component \(H\) of \(G^*\), then assume that \(|N_G(u) \cap H| \ge |N_G(w) \cap H|\), that is, \(H\) contains at least as many neighbours of \(u\) as neighbours of \(w\) (see Figure 16.2).

Figure 16.2: Coming soon!

Let \(G^{**}\) be the graph obtained from \(G^*\) by deleting all edges incident to \(w\). Clearly, \(G^{**}\) is a cluster graph. We show that \(G^{**}\) can be obtained from \(G\) using at most \(k\) edge edits. Since one of these edge edits is the deletion of the edge \((v,w)\), it can thus be obtained from \(G_{v,w}\) using at most \(k-1\) edge edits, that is, \((G_{v,w},k-1)\) is a yes-instance.

We divide the set of edge edits \(M^*\) that produce \(G^*\) from \(G\) into two subsets:

• \(M_1^*\): The addition of all edges between \(w\) and vertices in \(H \setminus N_G(w)\) and
• \(M_2^*\): All remaining edge edits.

The set of edge edits \(M^{**}\) that produce \(G^{**}\) from \(G\) can similarly be divided into

• \(M_1^{**}\): The deletion of all edges between \(w\) and vertices in \(H \cap N_G(w)\) and
• \(M_2^*\): All remaining edge edits.

Note that this last item is not a typo: This is indeed the same subset \(M_2^*\) of \(M^*\) because \(G^{*}\) and \(G^{**}\) contain the same set of edges not incident to \(w\). Thus, it suffices to prove that \(|M_1^{**}| \le |M_1^*|\) because this implies that \(|M^{**}| = |M_1^{**}| + |M_2^*| \le |M_1^*| + |M_2^*| = |M^*| \le k\).

We have \(|M_1^*| = |H| - |N_G(w) \cap H|\) and \(|M_1^{**}| = |N_G(w) \cap H|\). Thus, \(|M_1^{**}| \le |M_1^*|\) if \(|N_G(w) \cap H| \le |H| - |N_G(w) \cap H|\), that is, if \(|N_G(w) \cap H| \le \frac{|H|}{2}\). However, if this is not the case, then the choice of \(w\) implies that \(|N_G(u) \cap H| \ge |N_G(w) \cap H| > \frac{|H|}{2} = \frac{|H \setminus \{u,w\}|}{2} + 1\). Since \(N_G(u) \cap H \subseteq H \setminus \{u,w\}\) and \(N_G(w) \cap H \subseteq H \setminus \{u,w\}\), this implies that \(|N_G(u) \cap N_G(w)| \ge 2\), that is, \(u\) and \(w\) have a common neighbour other than \(v\), a contradiction. ▨