{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T08:20:49Z","timestamp":1715934049988},"reference-count":51,"publisher":"PeerJ","license":[{"start":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T00:00:00Z","timestamp":1675987200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62101125, 72122006"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"crossref","award":["SBK2020040023"],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["2242022R40067, 2242022K30007"],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"Given a directed graph G<\/jats:italic> = (V, E<\/jats:italic>), a feedback vertex set is a vertex subset C<\/jats:italic> whose removal makes the graph G<\/jats:italic> acyclic. The feedback vertex set problem is to find the subset C<\/jats:italic>* whose cardinality is the minimum. As a general model, this problem has a variety of applications. However, the problem is known to be NP-hard, and thus computationally challenging. To solve this difficult problem, this article develops an iterated dynamic thresholding search algorithm, which features a combination of local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs from various sources demonstrate the advantage of the algorithm compared with the state-of-the-art algorithms, by reporting record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. We also study how the key components of the algorithm affect its performance of the algorithm.<\/jats:p>","DOI":"10.7717\/peerj-cs.1245","type":"journal-article","created":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T09:55:55Z","timestamp":1676022955000},"page":"e1245","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic thresholding search for the feedback vertex set problem"],"prefix":"10.7717","volume":"9","author":[{"given":"Wen","family":"Sun","sequence":"first","affiliation":[{"name":"School of Cyber Science and Engineering, Southeast University, Nanjing, China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8813-4377","authenticated-orcid":true,"given":"Jin-Kao","family":"Hao","sequence":"additional","affiliation":[{"name":"LERIA, Universit\u00e9 d\u2019Angers, Angers, France"}]},{"given":"Zihao","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Engineering, Southeast University, Nanjing, China"}]},{"given":"Wenlong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Engineering, Southeast University, Nanjing, China"}]},{"given":"Qinghua","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Management, Huazhong University of Science and Technology, Wuhan, China"}]}],"member":"4443","published-online":{"date-parts":[[2023,2,10]]},"reference":[{"key":"10.7717\/peerj-cs.1245\/ref-1","volume-title":"Digraphs: theory, algorithms and applications","author":"Bangjensen","year":"2008"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-2","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","article-title":"Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference","volume":"27","author":"Bar-Yehuda","year":"1998","journal-title":"SIAM Journal on Computing"},{"key":"10.7717\/peerj-cs.1245\/ref-3","first-page":"65","article-title":"On directed feedback vertex set parameterized by treewidth","author":"Bonamy","year":"2018"},{"key":"10.7717\/peerj-cs.1245\/ref-4","first-page":"1929","article-title":"Combinational profiles of sequential benchmark circuits","author":"Brglez","year":"1989"},{"issue":"16\u201317","key":"10.7717\/peerj-cs.1245\/ref-5","doi-asserted-by":"publisher","first-page":"e750","DOI":"10.7717\/peerj-cs.750","article-title":"Approaching the bi-objective critical node detection problem with a smart initialization-based evolutionary algorithm","volume":"7","author":"B\u00e9czi","year":"2021","journal-title":"PeerJ Computer Science"},{"issue":"6","key":"10.7717\/peerj-cs.1245\/ref-6","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1137\/S0097539798338163","article-title":"An approximation algorithm for feedback vertex sets in tournaments","volume":"30","author":"Cai","year":"2001","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.3969\/j.issn.1000-3428.2006.04.023","article-title":"Search algorithm for computing minimum feedback vertex set of a directed graph","volume":"32","author":"Cai","year":"2006","journal-title":"Computer Engineering"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s10479-014-1720-5","article-title":"Iterated responsive threshold search for the quadratic multiple knapsack problem","volume":"226","author":"Chen","year":"2015","journal-title":"Annals of Operations Research"},{"issue":"1\u20132","key":"10.7717\/peerj-cs.1245\/ref-9","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.engappai.2019.03.015","article-title":"Dynamic thresholding search for minimum vertex cover in massive sparse graphs","volume":"82","author":"Chen","year":"2019","journal-title":"Engineering Applications of Artificial Intelligence"},{"key":"10.7717\/peerj-cs.1245\/ref-10","first-page":"177","article-title":"A fixed-parameter algorithm for the directed feedback vertex set problem","author":"Chen","year":"2008"},{"key":"10.7717\/peerj-cs.1245\/ref-11","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"key":"10.7717\/peerj-cs.1245\/ref-12","first-page":"343","article-title":"Tabu thresholding for the frequency assignment problem","volume-title":"Meta-Heuristics","author":"Diane","year":"1996"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0021-9991(90)90201-B","article-title":"Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing","volume":"90","author":"Dueck","year":"1990","journal-title":"Journal of Computational Physics"},{"issue":"1\u20132","key":"10.7717\/peerj-cs.1245\/ref-14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","article-title":"On the maximal number of disjoint circuits of a graph","volume":"9","author":"Erd\u0151s","year":"1962","journal-title":"Publicationes Mathematicae Debrecen"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","article-title":"Approximating minimum feedback sets and multicuts in directed graphs","volume":"20","author":"Even","year":"1998","journal-title":"Algorithmica"},{"key":"10.7717\/peerj-cs.1245\/ref-16","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","article-title":"Feedback set problems","volume-title":"Handbook of Combinatorial Optimization","author":"Festa","year":"1999"},{"issue":"3","key":"10.7717\/peerj-cs.1245\/ref-17","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10884-013-9312-7","article-title":"Dynamics and control at feedback vertex sets. I: informative and determining nodes in regulatory networks","volume":"25","author":"Fiedler","year":"2013","journal-title":"Journal of Dynamics and Differential Equations"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3284176","article-title":"Exact algorithms via monotone local search","volume":"66","author":"Fomin","year":"2019","journal-title":"Journal of the ACM (JACM)"},{"key":"10.7717\/peerj-cs.1245\/ref-19","first-page":"184","article-title":"Finding a minimum feedback vertex set in time O(1.7548n)","author":"Fomin","year":"2006"},{"issue":"5","key":"10.7717\/peerj-cs.1245\/ref-20","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s10732-013-9224-z","article-title":"Applying local search to the feedback vertex set problem","volume":"19","author":"Galinier","year":"2013","journal-title":"Journal of Heuristics"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-21","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1002\/jgt.21631","article-title":"Feedback vertex sets in tournaments","volume":"72","author":"Gaspers","year":"2013","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-22","doi-asserted-by":"publisher","first-page":"026107","DOI":"10.1103\/PhysRevE.65.026107","article-title":"Growing scale-free networks with tunable clustering","volume":"65","author":"Holme","year":"2002","journal-title":"Physical Review E"},{"key":"10.7717\/peerj-cs.1245\/ref-23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume-title":"Complexity of Computer Computations","author":"Karp","year":"1972"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-24","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.ejor.2021.08.044","article-title":"Iterated dynamic thresholding search for packing equal circles into a circular container","volume":"299","author":"Lai","year":"2022","journal-title":"European Journal of Operational Research"},{"issue":"9","key":"10.7717\/peerj-cs.1245\/ref-25","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1109\/TC.1979.1675435","article-title":"On minimum cost recovery from system deadlock","volume":"28","author":"Leung","year":"1979","journal-title":"IEEE Transactions on Computers"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-26","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/0196-6774(88)90013-2","article-title":"A contraction algorithm for finding small cycle cutsets","volume":"9","author":"Levy","year":"1988","journal-title":"Journal of Algorithms"},{"key":"10.7717\/peerj-cs.1245\/ref-27","first-page":"364","article-title":"Computing minimum feedback vertex sets by contraction operations and its applications on cad","author":"Lin","year":"1999"},{"issue":"7346","key":"10.7717\/peerj-cs.1245\/ref-28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1038\/nature10011","article-title":"Controllability of complex networks","volume":"473","author":"Liu","year":"2011","journal-title":"Nature"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3461477","article-title":"2-approximating feedback vertex set in tournaments","volume":"17","author":"Lokshtanov","year":"2021","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3155299","article-title":"Linear time parameterized algorithms for subset feedback vertex set","volume":"14","author":"Lokshtanov","year":"2018","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-31","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","article-title":"The irace package: iterated racing for automatic algorithm configuration","volume":"3","author":"L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","journal-title":"Operations Research Perspectives"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-32","doi-asserted-by":"publisher","first-page":"e699","DOI":"10.7717\/peerj-cs.699","article-title":"Abcde: Approximating betweenness-centrality ranking with progressive-dropedge","volume":"7","author":"Mirakyan","year":"2021","journal-title":"PeerJ Computer Science"},{"key":"10.7717\/peerj-cs.1245\/ref-33","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1511.01137","article-title":"A 7\/3-approximation for feedback vertex sets in tournaments","author":"Mnich","year":"2015","journal-title":"ArXiv preprint"},{"key":"10.7717\/peerj-cs.1245\/ref-34","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.jtbi.2013.06.009","article-title":"Dynamics and control at feedback vertex sets. II: a faithful monitor to determine the diversity of molecular activities in regulatory networks","volume":"335","author":"Mochizuki","year":"2013","journal-title":"Journal of Theoretical Biology"},{"key":"10.7717\/peerj-cs.1245\/ref-35","first-page":"315","article-title":"Four approximation algorithms for the feedback vertex set problem","author":"Monien","year":"1981"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-36","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1017\/S0013091500009639","article-title":"On maximal transitive subtournaments","volume":"17","author":"Moon","year":"1971","journal-title":"Proceedings of the Edinburgh Mathematical Society"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-37","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0375-9601(90)90166-L","article-title":"Stochastic versus deterministic update in simulated annealing","volume":"146","author":"Moscato","year":"1990","journal-title":"Physics Letters A"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-38","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF00993315","article-title":"An optimal algorithm for cycle breaking in directed graphs","volume":"7","author":"Orenstein","year":"1995","journal-title":"Journal of Electronic Testing"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-39","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1023\/A:1009736921890","article-title":"A greedy randomized adaptive search procedure for the feedback vertex set problem","volume":"2","author":"Pardalos","year":"1998","journal-title":"Journal of Combinatorial Optimization"},{"issue":"11","key":"10.7717\/peerj-cs.1245\/ref-40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjb\/e2014-50289-7","article-title":"Solving the undirected feedback vertex set problem by local search","volume":"87","author":"Qin","year":"2014","journal-title":"The European Physical Journal B"},{"key":"10.7717\/peerj-cs.1245\/ref-41","first-page":"160","article-title":"Exact computation of maximum induced forest","author":"Razgon","year":"2006"},{"key":"10.7717\/peerj-cs.1245\/ref-42","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1142\/9789812770998_0010","article-title":"Computing minimum directed feedback vertex set in o*(1.9977n)","volume-title":"Theoretical Computer Science","author":"Razgon","year":"2007"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-43","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"Seymour","year":"1995","journal-title":"Combinatorica"},{"key":"10.7717\/peerj-cs.1245\/ref-44","volume-title":"Operating system concepts","author":"Silberschatz","year":"2006"},{"key":"10.7717\/peerj-cs.1245\/ref-45","doi-asserted-by":"publisher","first-page":"12353","DOI":"10.1109\/ACCESS.2017.2724065","article-title":"Nonuniform neighborhood sampling based simulated annealing for the directed feedback vertex set problem","volume":"5","author":"Tang","year":"2017","journal-title":"IEEE Access"},{"issue":"1","key":"10.7717\/peerj-cs.1245\/ref-46","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/S0377-2217(02)00669-0","article-title":"A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem","volume":"152","author":"Tarantilis","year":"2004","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"10.7717\/peerj-cs.1245\/ref-47","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/3149.3159","article-title":"Feedback vertex sets and cyclically reducible graphs","volume":"32","author":"Wang","year":"1985","journal-title":"Journal of the Association of Computing Machinery"},{"issue":"28","key":"10.7717\/peerj-cs.1245\/ref-48","doi-asserted-by":"publisher","first-page":"7234","DOI":"10.1073\/pnas.1617387114","article-title":"Structure-based control of complex networks with nonlinear dynamics","volume":"114","author":"Za\u00f1udo","year":"2017","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"issue":"12","key":"10.7717\/peerj-cs.1245\/ref-49","doi-asserted-by":"publisher","first-page":"3492","DOI":"10.1109\/TCSII.2020.2997974","article-title":"The feedback vertex set problem of multiplex networks","volume":"67","author":"Zhao","year":"2020","journal-title":"IEEE Transactions on Circuits and Systems II: Express Briefs"},{"issue":"7","key":"10.7717\/peerj-cs.1245\/ref-50","doi-asserted-by":"publisher","first-page":"73303","DOI":"10.1088\/1742-5468\/2016\/07\/073303","article-title":"A spin glass approach to the directed feedback vertex set problem","volume":"2016","author":"Zhou","year":"2016","journal-title":"Journal of Statistical Mechanics: Theory and Experiment"},{"issue":"4","key":"10.7717\/peerj-cs.1245\/ref-51","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.ins.2021.04.014","article-title":"Responsive threshold search based memetic algorithm for balanced minimum sum-of-squares clustering","volume":"569","author":"Zhou","year":"2021","journal-title":"Information Sciences"}],"container-title":["PeerJ Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/peerj.com\/articles\/cs-1245.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-1245.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-1245.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-1245.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T09:56:18Z","timestamp":1676022978000},"score":1,"resource":{"primary":{"URL":"https:\/\/peerj.com\/articles\/cs-1245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,10]]},"references-count":51,"alternative-id":["10.7717\/peerj-cs.1245"],"URL":"https:\/\/doi.org\/10.7717\/peerj-cs.1245","archive":["CLOCKSS","LOCKSS","Portico"],"relation":{"has-review":[{"id-type":"doi","id":"10.7287\/peerj-cs.1245v0.1\/reviews\/2","asserted-by":"object"},{"id-type":"doi","id":"10.7287\/peerj-cs.1245v0.2\/reviews\/2","asserted-by":"object"},{"id-type":"doi","id":"10.7287\/peerj-cs.1245v0.1\/reviews\/1","asserted-by":"object"}]},"ISSN":["2376-5992"],"issn-type":[{"value":"2376-5992","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,10]]},"article-number":"e1245"}}
