# An FPT Algorithm for Directed Co-Graph Edge Deletion
## 4 Our Results
For Case 2.1, we apply the following branching rule, where the branching vector is \((1,1,2)\) and the corresponding branching factor is \(1+\sqrt{2}<2.4143\):  
* \(\{-bc\}\)
* \(\{-cd\}\)
* \(\{-vb,-ab\}\)  
For Case 2.2, we apply the following branching rule, where the branching vector is \((1,2,2,2,2)\) and the corresponding branching factor is \(\frac{1+\sqrt{17}}{2}<2.5616\):  
* \(\{-cd\}\)
* \(\{-va,-ab\}\)
* \(\{-va,-bc\}\)
* \(\{-vc,-ab\}\)
* \(\{-vc,-bc\}\)  
For Case 2.3, we apply the following branching rule, where the branching vector is \((1,2,2,2,2)\) and the corresponding branching factor is \(\frac{1+\sqrt{17}}{2}<2.5616\):  
* \(\{-ab\}\)
* \(\{-vb,-bc\}\)
* \(\{-vb,-cd\}\)
* \(\{-vd,-bc\}\)
* \(\{-vd,-cd\}\)  
For Case 2.4, we apply the following branching rule, where the branching vector is \((1,1,2)\) and the corresponding branching factor is \(1+\sqrt{2}<2.4143\):  
* \(\{-ab\}\)
* \(\{-bc\}\)
* \(\{-vc,-cd\}\)  
**Case 3: \(v\) has exactly three neighbors from \(H\). **  
All subcases that need to be considered are shown in Figure 3.5  
Figure 3.6 Four cases that need to be considered when a vertex \(v\) is adjacent to two vertices in an induced \(D_{8}\). For Case 3.1, we apply the following branching rule, which has a branching vector of \((1,2,2,3,3)\) and a corresponding maximum branching factor of \(2.2696\):  
* \(\{-cd\}\)
* \(\{-va,-ab\}\)
* \(\{-va,-bc,-vb\}\)
* \(\{-vc,-bc\}\)
* \(\{-vc,-ab,-vb\}\)  
For Case 3.2, we apply the following branching rule, which has a branching vector of \((2,2,2,2,3,3,3)\) and a corresponding maximum branching factor of \(2.3830\):  
* \(\{-bc,-vd\}\)
* \(\{-cd,-vd\}\)
* \(\{-cd,-vb,-va\}\)
* \(\{-cd,-vb\}\)
* \(\{-ab,-va\}\)
* \(\{-ab,-vb,-vd\}\)  
For Case 3.3, we apply the following branching rule, which has a branching vector of \((2,2,2,3,3,3,3)\) and a corresponding maximum branching factor of \(2.2696\):  
* \(\{-cd,-vc,-av\}\)
* \(\{-cd,-vc,-ab\}\)
* \(\{-cd,-vd\}\)
* \(\{-vc,-bc,-vd\}\)
* \(\{-va,-bc\}\)
* \(\{-ab,-va\}\)
* \(\{-vc,-ab,-vd\}\)  
For Case 3.4, we apply the following branching rule, which has a branching vector of \((1,2,2,3,3)\) and a corresponding maximum branching factor of \(2.2696\):  
* \(\{-cd,-vc,-av\}\)
* \(\{-cd,-vc,-ab\}\)
* \(\{-cd,-vd\}\)
* \(\{-vc,-bc,-vd\}\)
* \(\{-va,-bc\}\)
* \(\{-ab,-bc\}\)
* \(\{-ab,-va\}\)
* \(\{-vc,-ab,-vd\}\)  
For Case 3.4, we apply the following branching rule, which has a branching vector of \((1,2,2,3,3)\) and a corresponding maximum branching factor of \(2.2696\):  
Figure 3.7 Four cases that need to be considered when a vertex \(v\) is adjacent to exactly three vertices in an induced \(D_{8}\). \(\bullet\)\(\{-ab\}\)\(\bullet\)\(\{-vb,-bc\}\)\(\bullet\)\(\{-vb,-cd,-vc\}\)\(\bullet\)\(\{-vd,-bc,-vc\}\)\(\bullet\)\(\{-vd,-cd\}\)  
**Case 4: \(v\) is adjacent to all vertices of \(H\). **  
Let us consider a graph where none of the branching rules introduced so far are applicable, which is called a reduced graph. It is easy to verify that in a reduced graph, for any induced \(D_{8}\) and any vertex \(v\) adjacent to all vertices of \(D_{8}\), the subgraph induced by the vertex \(v\) and the \(D_{8}\) is isomorphic to one of the graphs in Figure 3.8 Two important observations are formulated below. **Observation 1**. : _Let \(G\) be a reduced graph. Then, all induced \(D_{8}\)s in \(G\) are pairwise vertex disjoint._  
**Observation 2**. : _Let \(G\) be a reduced graph. Then, deleting any edge from an induced \(D_{8}\) in \(G\) does not yield any new induced forbidden structures (\(D_{1}\)-\(D_{8}\))._  
Let \(i\) be the number of all induced \(D_{8}\) in a reduced graph \(G\). By Observation 1, we need to delete \(i\) edges to destroy all the induced \(D_{8}\)s in \(G\). By Observation 2, the resulting graph is a directed co-graph. In light of this fact, when we arrive at a reduced graph at a branching node, we determine that the given instance is a YES-instance if there are, at most, \(k\) induced \(D_{8}\)s in the reduced graph.