16.4.1.2. Case 2

In this case, assume that we make the recursive calls in the order \((G_{u,w}, k-1)\), \((G_{u,v}, k-1)\), \((G_{v,w}, k-1)\) (see Figure 16.3.

Figure 16.3: Coming soon!

Let us call these branches 1, 2, and 3. This has no bearing on the behaviour of the algorithm but aids the exposition. Branch 2 removes the edge \((u, v)\) and thus creates the conflict triple \((u, x, v)\). We choose to branch on this triple in this recursive call. Since we just removed the edge \((u, v)\), there is no point in attempting to add it again. Thus, the second recursive call needs to branch only on the two instances obtained by removing \((u, x)\) or \((x, v)\). Let us call these branches 2.1 and 2.2. Finally, \((u, x, w)\) is a conflict triple in branch 2.2. The key observation now is that the order in which we add or remove edges to or from \(G\) is unimportant. Thus, branch 2.2 does not need to consider adding the edge \((u, w)\) because this option is already considered in branch 1. Branch 2.2 also does not need to consider removing the edge \((u, x)\) because this option is already considered in branch 2.1. Thus, branch 2.2 makes only one recursive call corresponding to removing the edge \((x, w)\). A similar analysis leads to branch 3 having two sub-branches 3.1 and 3.2, where branch 3.2 makes only one recursive call. By collapsing all these recursive calls into a single invocation that makes 5 recursive calls corresponding to branches 1, 2.1, 2.2.1, 3.1, and 3.2.1, we obtain an algorithm that makes recursive calls on the following 5 instances corresponding to the leaves of the tree in Figure 16.3:

• \((G_1, k-1)\), where \(G_1 = G_{u,w}\) is obtained from \(G\) by adding the edge \((u, w)\),
• \((G_{2.1}, k-2)\), where \(G_{2.1}\) is obtained from \(G\) by removing the edges \((u, v)\) and \((u, x)\),
• \((G_{2.2.1}, k-3)\), where \(G_{2.2.1}\) is obtained from \(G\) by removing the edges \((u, v)\), \((v, x)\), and \((w, x)\),
• \((G_{3.1}, k-2)\), where \(G_{3.1}\) is obtained from \(G\) by removing the edges \((v, w)\) and \((w, x)\), and
• \((G_{3.2.1}, k-3)\), where \(G_{3.2.1}\) is obtained from \(G\) by removing the edges \((v, w)\), \((v, x)\), and \((u, x)\).

The following lemma follows immediately from this discussion:

Lemma 16.14: \((G, k)\) is a yes-instance for the cluster editing problem if and only if one of the instances \((G_1, k-1)\), \((G_{2.1}, k-2)\), \((G_{2.2.1}, k-3)\), \((G_{3.1}, k-2)\) or \((G_{3.2.1}, k-3)\) is.

Lemma 16.14 provides a branching rule with branching vector \((1, 2, 3, 2, 3)\) and thus with branching number less than 2.27.