We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An FPT Algorithm for Directed Co-Graph Edge Deletion.
- Authors
Li, Wenjun; Yang, Xueying; Xu, Chao; Yang, Yongjie
- 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) .
- Subjects
DIRECTED graphs; ALGORITHMS; NP-hard problems; INTEGERS
- Publication
Algorithms, 2024, Vol 17, Issue 2, p69
- ISSN
1999-4893
- Publication type
Article
- DOI
10.3390/a17020069