{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T04:06:50Z","timestamp":1767845210062,"version":"3.49.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0430683CCF-0830455"],"award-info":[{"award-number":["CCF-0430683CCF-0830455"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>\n            The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph\n            <jats:italic>G<\/jats:italic>\n            and a parameter\n            <jats:italic>k<\/jats:italic>\n            , either construct a feedback vertex set of at most\n            <jats:italic>k<\/jats:italic>\n            vertices in\n            <jats:italic>G<\/jats:italic>\n            or report that no such a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            for some function\n            <jats:italic>f<\/jats:italic>\n            . In this article, we develop new algorithmic techniques that result in an algorithm with running time 4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            !\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            for the DFVS problem. Therefore, we resolve this open problem.\n          <\/jats:p>","DOI":"10.1145\/1411509.1411511","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":142,"title":["A fixed-parameter algorithm for the directed feedback vertex set problem"],"prefix":"10.1145","volume":"55","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[{"name":"Texas A&amp;M University, College Station, Texas"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, College Station, Texas"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Songjian","family":"Lu","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, College Station, Texas"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barry","family":"O'sullivan","sequence":"additional","affiliation":[{"name":"University College Cork, Cork, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[{"name":"University College Cork, Cork, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,11,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1001"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763464"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789710"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Chen J. Fomin F. Liu Y. Lu S. and \n      Villanger Y\n  . \n  2007\n  a. Improved algorithms for the feedback vertex set problems. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) Lecture Notes in Computer Science vol. \n  4619\n  . \n  Springer-Verlag New York 422--433.   Chen J. Fomin F. Liu Y. Lu S. and Villanger Y. 2007a. Improved algorithms for the feedback vertex set problems. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) Lecture Notes in Computer Science vol. 4619. Springer-Verlag New York 422--433.","DOI":"10.1007\/978-3-540-73951-7_37"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Chen J. Liu Y. and \n      Lu S\n  . \n  2007\n  b. An improved parameterized algorithm for the minimum node multiway cut problem. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) Lecture Notes in Computer Science vol. \n  4619\n  . \n  Springer-Verlag New York 495--506.   Chen J. Liu Y. and Lu S. 2007b. An improved parameterized algorithm for the minimum node multiway cut problem. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) Lecture Notes in Computer Science vol. 4619. Springer-Verlag New York 495--506.","DOI":"10.1007\/978-3-540-73951-7_43"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 7th Annual Structural Complexity Conference. IEEE Computer Society Press","author":"Downey R."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer-Verlag New York.   Downey R. and Fellows M. 1999. Parameterized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_2_2_13_1","unstructured":"Gardarin G. and Spaccapietra S. 1976. Integrity of databases: A general lockout algorithm with deadlock avoidance. In Modeling in Data Base Management System G Nijsssen Ed. North-Holland Amsterdam The Netherlands 395--411.  Gardarin G. and Spaccapietra S. 1976. Integrity of databases: A general lockout algorithm with deadlock avoidance. In Modeling in Data Base Management System G Nijsssen Ed. North-Holland Amsterdam The Netherlands 395--411."},{"key":"e_1_2_2_14_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman New York.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman New York."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_15"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm039"},{"key":"e_1_2_2_18_1","volume-title":"Complexity of Computer Computations","author":"Karp R."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759032"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/318593.318622"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_2_23_1","volume-title":"Combinatorial Optimization","author":"Schrijver A."},{"key":"e_1_2_2_24_1","unstructured":"Silberschatz A. and Galvin P. 1994. Operating System Concepts 4th ed. Addison Wesley Reading MA.   Silberschatz A. and Galvin P. 1994. Operating System Concepts 4th ed. Addison Wesley Reading MA."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1411509.1411511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:29Z","timestamp":1750253369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1411509.1411511"],"URL":"https:\/\/doi.org\/10.1145\/1411509.1411511","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}