{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:43:47Z","timestamp":1760143427201,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T00:00:00Z","timestamp":1707091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["62372066","62372394","62002032","2022JJ30620","CX20220944"],"award-info":[{"award-number":["62372066","62372394","62002032","2022JJ30620","CX20220944"]}]},{"name":"Natural Science Foundation of Hunan Province of China","award":["62372066","62372394","62002032","2022JJ30620","CX20220944"],"award-info":[{"award-number":["62372066","62372394","62002032","2022JJ30620","CX20220944"]}]},{"name":"Postgraduate Scientific Research Innovation Project of Hunan Province","award":["62372066","62372394","62002032","2022JJ30620","CX20220944"],"award-info":[{"award-number":["62372066","62372394","62002032","2022JJ30620","CX20220944"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.733k), which is significantly more efficient compared to the brute-force algorithm, which has a running time of O(6k).<\/jats:p>","DOI":"10.3390\/a17020069","type":"journal-article","created":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T05:36:43Z","timestamp":1707197803000},"page":"69","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An FPT Algorithm for Directed Co-Graph Edge Deletion"],"prefix":"10.3390","volume":"17","author":[{"given":"Wenjun","family":"Li","sequence":"first","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xueying","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Economics, Saarland University, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"100556","DOI":"10.1016\/j.cosrev.2023.100556","article-title":"A Survey of Parameterized Algorithms and the Complexity of Edge modification","volume":"48","author":"Crespelle","year":"2023","journal-title":"Comput. Sci. Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"162401","DOI":"10.1007\/s11704-020-0137-3","article-title":"An Improved Branching Algorithm for the Proper Interval Edge Deletion Problem","volume":"16","author":"Li","year":"2022","journal-title":"Front. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.tcs.2015.01.049","article-title":"Edge Deletion Problems: Branching Facilitated by Modular Decomposition","volume":"573","author":"Liu","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/3-540-62950-5_74","article-title":"A Complete Axiomatisation for the Inclusion of Series-Parallel Partial Orders","volume":"Volume 1232","author":"Comon","year":"1997","journal-title":"Proceedings of the Rewriting Techniques and Applications, 8th International Conference, RTA-97"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","article-title":"Fully Dynamic Recognition Algorithm and Certificate for Directed Cographs","volume":"154","author":"Crespelle","year":"2006","journal-title":"Discret. Appl. Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","article-title":"The Complexity of Some Edge Deletion Problems","volume":"35","author":"Colbourn","year":"1988","journal-title":"IEEE Trans. Circuits Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1250008","DOI":"10.1142\/S1793830912500085","article-title":"Bounded Search Tree Algorithms for Parametrized Cograph Deletion: Efficient Branching Rules by Exploiting Structures of Special Graph Classes","volume":"4","author":"Nastos","year":"2012","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1007\/s00453-012-9619-5","article-title":"On the (Non-)Existence of Polynomial Kernels for Pl-Free Edge Modification Problems","volume":"65","author":"Guillemot","year":"2013","journal-title":"Algorithmica"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1137\/060664690","article-title":"A Simple Linear Time LexBFS Cograph Recognition Algorithm","volume":"22","author":"Bretscher","year":"2008","journal-title":"SIAM J. Discret. Math."},{"key":"ref_10","unstructured":"Schmitz, Y., and Wanke, E. (2023). The Directed Metric Dimension of Directed Co-Graphs. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.tcs.2020.11.047","article-title":"How to Compute Digraph Width Measures on Directed Co-Graphs","volume":"855","author":"Gurski","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.19139\/soic.v5i1.260","article-title":"Dynamic Programming Algorithms on Directed Cographs","volume":"5","author":"Gurski","year":"2017","journal-title":"Stat. Optim. Inf. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/2\/69\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:55:11Z","timestamp":1760104511000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/2\/69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,5]]},"references-count":12,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["a17020069"],"URL":"https:\/\/doi.org\/10.3390\/a17020069","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,2,5]]}}}