# An FPT Algorithm for Directed Co-Graph Edge Deletion
## 4 Our Results
However, as this does not improve the worst-case branching factor, and the induced \(D\gamma\)s are handled by branching rules introduced later, to simplify the presentation, we do not discuss this improvement). 3. Deletion of the edge \(ad\) After deleting \(ad\), vertices \(a\), \(c\), and \(d\) form an induced \(D_{3}\), and since the deletion of \(ac\) is covered in Cases (1) and (2), we consider the deletion of \(cd\). Observe now that \(b\), \(c\), and \(d\) form an induced \(D_{2}\). If we delete \(bc\), then \(a\), \(b\), and \(c\) form an induced \(D_{2}\), implying that at least one of \(ab\) and \(ac\) needs to be deleted, which is covered in Cases (1) and (2). Therefore, we do not need to consider the case where \(bc\) is deleted. In other words, in this case, we need only the branching case \(\{-ad,-cd,-bd\}\). 4. Deletion of the edge \(bc\) The deletion of \(bc\) triggers the deletion of at least one of \(ab\) and \(ac\), both of which are covered by previous cases. 5. Deletion of the edge \(bd\) After deleting \(bd\), an induced \(D_{2}\) formed by \(a\), \(b\), and \(d\) and an induced \(D_{3}\) formed by \(b\), \(c\), and \(d\) occur. To destroy the \(D_{2}\), at least one of \(ab\) and \(ad\) needs to be deleted, both of which are covered by previous cases. 6. Deletion of the edge \(cd\) After deleting the edge \(cd\), the vertices \(b\), \(c\), and \(d\) form an induced \(D_{2}\), inviting the further deletion of at least one of \(bc\) and \(bd\), both of which are covered by previous cases. To summarize, to destroy \(D_{6}\), we apply the following branching rule, which has a branching vector of \((3,3,3,3,3,3,4)\) and a corresponding maximum branching factor of 1.870:  
* \(\{-ab,-ad,-ac\}\) \(\{-ab,-ad,-cd,-bc\}\) \(\{-ab,-bd,-cd\}\) \(\{-ab,-bd,-bc\}\) \(\{-ac,-bc,-ad\}\) \(\{-ac,-bc,-cd\}\) \(\{-ad,-cd,-bd\}\)  
Figure 4: An illustration of the branching cases for \(D_{6}\) when the edge \(ac\) is deemed to be deleted. Now, we consider the forbidden structures \(D_{7}\) and \(D_{8}\). We first apply branching rules satisfying the following condition: the deletion of some edges in an induced \(D_{7}\) or \(D_{8}\) results in a new induced \(D_{i}\)s, where \(i\in[3]\). Specifically, we assume that there is an induced \(D_{7}\) or \(D_{8}\) denoted by \(H\) in \(G\) so that the deletion of some edge \(xy\) from \(H\) results in an induced \(D_{i}\), where \(i\in[3]\), denoted by \(H^{\prime}\). Let \(v\) denote the third vertex in \(H^{\prime}\). It is clear that \(v\) is the middle vertex of \(H^{\prime}\) (i.e., the one with degree two in the underlying graph of \(H^{\prime}\)). Let \(e\) and \(e^{\prime}\) be the other two edges in \(H\) other than \(xy\). Then, we exert the following branching rule that has a branching factor \(1+\sqrt{3}<2.733\):  
* \(\{-e\}\)
* \(\{-ey,-vx\}\)
* \(\{-xy,-vy\}\)  
We continue our branching for \(D_{7}\) as follows. Let \(H\) be an induced \(D_{7}\). If \(H\) is a connected component, we directly delete it from \(G\) and decrease \(k\) by one. Assume now that there exists at least one vertex \(v\) not in \(H\) but adjacent to at least one vertex from \(H\). By symmetry, and by the assumption that none of the above-discussed branching rules are applicable, we need to consider the following cases. **Case 1: \(v\) has exactly one neighbor in \(H\). **  
We have two subcases to consider, as shown in Figure 5.  
In both subcases, there are indeed two induced \(D_{7}\)s; hence, deleting only one edge is insufficient. Specifically, for Case 1.1, we apply the following branching rule:  
* \(\{-ab\}\)
* \(\{-bc\}\)
* \(\{-av,-cd\}\)  
For Case 1.2, we apply the following branching rule:  
* \(\{-cd\}\)
* \(\{-bc\}\)
* \(\{-ab,-vb\}\)  
Both branching rules have the same branching vector of \((1,1,2)\) and a corresponding maximum branching factor of \(1+\sqrt{2}<2.4143\). **Case 2: \(v\) has exactly two neighbors in \(H\).