16.4.1.3. Case 3

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

Figure 16.4: Coming soon!

Let us call these branches 1, 2, and 3. Branch 2 considers the conflict triple \((u, v, x)\). Since branch 1 already considers the option of removing the edge \((u, v)\), branch 2 only needs to consider removing the edge \((u, x)\) or adding the edge \((v, x)\). Let us call these branches 2.1 and 2.2. Branch 2.2 considers the conflict triple \((v, w, x)\) created after adding the edge \((v, x)\). Since branch 2 removed the edge \((v, w)\) and branch 2.2 added the edge \((v, x)\), any child invocation of branch 2.2 does not need to consider adding the edge \((v, w)\) again or removing the edge \((v, x)\) again. Thus, the only way to resolve the conflict triple \((v, w, x)\) in branch 2.2 is to remove the edge \((w, x)\). Branch 3 considers the conflict triple \((u, v, x)\). Since branch 1 already considers the option of removing the edge \((u, v)\), branch 3 only needs to consider removing the edge \((u, x)\) or adding the edge \((v, x)\). Let us call these branches 3.1 and 3.2. Branch 3.1 removes the edge \((u, x)\) and then considers the conflict triple \((u, w, x)\). Since we just removed the edge \((u, x)\) and branch 3 added the edge \((u, w)\), the only way to resolve this conflict triple in branch 3.2 is to remove the edge \((w, x)\). By collapsing these recursive calls into a single invocation again, we obtain an invocation that makes recursive calls on the following 5 instances corresponding to the leaves of the tree in Figure 16.4:

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

Once again, the following lemma follows immediately from the discussion above:

Lemma 16.15: \((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.1}, k-2)\) or \((G_{3.2}, k-3)\) is.

The branching vector of Case 3 is \((1, 2, 3, 3, 2)\), which gives the same branching number less than 2.27 as in Case 2.

Since the three cases of the algorithm have branching numbers 2, 2.27, and 2.27, the algorithm runs in \(O^*\bigl(2.27^k\bigr)\) time.

Theorem 16.16: It takes \(O^*\bigl(2.27^k\bigr)\) time to decide whether a given instance \((G, k)\) is a yes-instance of the cluster editing problem and, if so, find a minimum cluster edit set for \(G\).