# An FPT Algorithm for Directed Co-Graph Edge Deletion
###### Abstract  
In the directed co-graph edge-deletion problem, we are given a directed graph and an integer \(k\), and the question is whether we can delete, at most, \(k\) edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions. Firstly, we show that the problem is NP-hard. Then, we show that directed co-graphs are fully characterized by eight forbidden structures, each having, at most, six edges. Based on the symmetry properties and several refined observations, we develop a branching algorithm with a running time of \(O(2.733^{k})\), which is significantly more efficient compared to the brute-force algorithm, which has a running time of \(O(6^{k})\).  
edge deletion; FPT algorithms; directed co-graphs; forbidden structures +
Footnote †: journal: _Algorithms_  
0000-0001-5000-0000-0000-00000-0000-0000-00000-00000-00000-00000-000000-000000-0000000000000000000000000000000000000000000000000  
graph can be transformed into a co-graph by deleting, at most, \(k\) edges (CGED) has been explored. Co-graphs are undirected graphs without paths of four vertices as induced graphs; thus, they are also named \(P_{4}\)-free graphs in the literature. It has long been known that CGED is NP-hard [6]. As each \(P_{4}\) contains exactly three edges, a naive branching algorithm solves CGED in time \(O(3^{k})\). After several rounds of improvement, the current best FPT algorithm for CGED has a running time of \(O(2.56^{k})\)[7]. It is important to mention that CGED also admits a cubic-vertex kernel [8]. The motivation behind this study is that many NP-hard problems have been found to be polynomial-time solvable when restricted to co-graphs, and co-graphs can be recognized in linear time [9].  
In this paper, we embark on an exploration of the DCGED problem. Our motivation is analogous: many directed graph problems, which are NP-hard in general, become polynomial-time solvable when restricted to directed co-graphs [10; 11; 12], and directed co-graphs can be recognized efficiently [5]. For the edge-deletion problem of a graph class, more effective branch rules can significantly reduce the size of the search tree, thereby reducing the overall running time of the branch algorithm. Obviously, the size of the search tree obtained by the branch algorithm of the DCGED problem is dominated by the largest forbidden subgraph. As the largest forbidden structure in a directed co-graph, \(D_{8}\) contains six edges. Therefore, there exists a straightforward branch-and-bound algorithm that solves the problem in time \(O(6^{k})\). In this paper, based on some detailed observation results, we can effectively improve the algorithm. Our branch algorithm adopts two important ideas: The first one is to consider a vertex that has a structural relationship with the forbidden subgraph and branch based on its different structural relationships with the forbidden subgraph. Considering more refined structural relationships will lead to more effective branching rules. The second point is based on an observation that we find some structural connections between the forbidden subgraphs. That is, deleting an edge in a larger forbidden subgraph may result in exporting another forbidden subgraph. At this point, in order to destroy the newly generated forbidden subgraph, another round of branching must be executed. Even some forbidden subgraphs may induce a branching chain. Combining such a branching strategy can significantly improve the branching rules of the problem. Based on these two ideas and some important properties, we derive an improved algorithm for the DCGED problem running in time \(O(2.733^{k})\).