16.4.1. Cluster Editing

Recall that the simple branching algorithm for cluster editing presented in Section 16.2.2 considers a conflict triple \((u, v, w)\) such that \((u, v), (v, w) \in E\) and \((u, w) \notin E\) and makes three recursive calls on instances \((G_{u,v}, k-1)\), \((G_{v,w}, k-1)\), and \((G_{u,w}, k-1)\), where \(G_{u,v}\) and \(G_{v,w}\) are obtained from \(G\) by removing the edge \((u,v)\) or \((v,w)\), respectively, and \(G_{u,w}\) is obtained from \(G\) by adding the edge \((u,w)\). The starting point for obtaining a faster algorithm is a careful case analysis consisting of three cases (see Figure 16.1):

• Case 1: There exists no vertex \(x \ne v\) that is adjacent to both \(u\) and \(w\).
• Case 2: There exists a vertex \(x \ne v\) that is adjacent to \(u\) and \(w\) and \((v, x) \in E\).
• Case 3: There exists a vertex \(x \ne v\) that is adjacent to \(u\) and \(w\) but \((v, x) \notin E\).

Figure 16.1: Coming soon!