# An FPT Algorithm for Directed Co-Graph Edge Deletion
## 4 Our Results  
We first show the NP-hardness of DCGED, and we then present our algorithm for DCGED. Theorem 1: _DCGED is NP-hard._  
Proof: Let \((G,k)\) be an instance of CGED. Recall that this problem determines whether we can remove, at most, \(k\) edges from \(G\) so that the resulting graph contains no paths of three edges as induced subgraphs. Let \(G^{\prime}\) be the digraph obtained from \(G\) by changing each edge \(uv\) with two arcs \((v,u)\) and \((u,v)\). Among all eight forbidden structures \(D_{1}\)-\(D_{8}\), only in \(D_{7}\) are all arcs bidirected; thus, it holds that there are, at most, \(k\) edges in \(G\) whose removal results in a co-graph, if and only if removing the corresponding \(k\) edges in \(G^{\prime}\) results in a directed co-graph. Then, the theorem follows from the NP-hardness of CGED [6]. Our second main contribution is a single exponential time algorithm for the DCGED problem based on branching. For a collection \(\{E_{1},E_{2},\ldots,E_{j}\}\) of subsets of edges, a branching rule that splits the instance into \(j\) subinstances, where the \(i\)-th subinstance, \(i\in[j]\), is obtained from the original instance by deleting exactly the edges in \(E_{i}\) and decreasing the parameter \(k\) by \(|E_{i}|\), is denoted by \(\{-E_{1},-E_{2},\ldots,-E_{j}\}\). Here, each \(-E_{i}\) is called a _branching case_ of the branching rule. For clarity, we use \(\{-e:e\in E_{i}\}\) to denote the branching case \(-E_{i}\); to describe a branching rule, we list all its branching cases, with one in each line. **Theorem 2**: _DCGED can be solved in time \(O(2.733^{k})\)._  
Proof. : Let \((G,k)\) be an instance of DCGED. We now discuss branching rules for the problem. We stress that the branching rules are iteratively applied to the instance in an order where, when a branching rule delineated below is applied, all rules introduced before are exhaustively applied. Clearly, direct branching on the edges of an induced \(D_{i}\), \(i\in[3]\) has a branching factor of 2, and direct branching on the edges of an induced \(D_{i}\), \(i\in\{4,5\}\) has a branching factor of 3. However, after deleting any edge in an induced \(D_{4}\) (\(D_{5}\)), at least one new induced \(D_{1}\), \(D_{2}\), or \(D_{3}\) emerges. Therefore, at least two edges need to be deleted in the induced \(D_{4}\) (\(D_{5}\)). Its branching vector is \((2,2,2)\), resulting in a branching rule with a branching factor of \(\sqrt{3}\), which is less than 1.733. Now, we proceed to the branching rules for \(D_{6}\). It can be observed that in order to destroy an induced \(D_{6}\) and some induced \(D_{1}\)-\(D_{5}\) occurring after the deletion of some edges in the \(D_{6}\), we need to delete at least three edges. To facilitate our analysis, let the vertices of an induced \(D_{6}\) be labeled as in Figure 2. The detailed branching cases are as follows. 1. Deletion of the edge \(ab\) After deleting \(ab\), vertices \(a\), \(d\), and \(b\) form an induced \(D_{3}\). The deletion of \(ad\) or \(bd\) will induce new forbidden structures, which will trigger the deletion of further edges. In particular, we have the following branching cases, as shown in Figure 3.  
Figure 3: An illustration of the branching cases for \(D_{6}\) when the edge \(ab\) is deemed to be deleted. Figure 2: An induced \(D_{6}\) used in the proof of Theorem 2. \(\bullet\) \(\{-ab,-ad,-ac\}\) \(\bullet\) \(\{-ab,-ad,-cd,-bc\}\) \(\bullet\) \(\{-ab,-bd,-cd\}\) \(\bullet\) \(\{-ab,-bd,-bc\}\)
2. Deletion of the edge \(ac\) After deleting \(ac\), \(\{a,b,c\}\) induces a \(D_{2}\) and \(\{a,c,d\}\) induces a \(D_{3}\). The deletion of \(ab\) is covered in Case (1). Thus, we need only to consider the deletion of edge \(bc\) to destroy the \(D_{2}\). It follows that the branching cases \(\{-ac,-bc,-ad\}\) and \(\{-ac,-bc,-cd\}\) cover all potential solutions where the edge \(ac\) is deleted, as shown in Figure 4 (in the first branching case, we obtain an induced \(D_{7}\), meaning that further edges need to be deleted.