{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:39:10Z","timestamp":1780439950813,"version":"3.54.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Netherlands Organization for Scientific Research","award":["639.021.438, and 024.002.003"],"award-info":[{"award-number":["639.021.438, and 024.002.003"]}]},{"name":"European Research Council","award":["617951"],"award-info":[{"award-number":["617951"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            In the Feedback Vertex Set (FVS) problem, one is given an undirected graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            , and one needs to determine whether there exists a set of\n            <jats:italic>k<\/jats:italic>\n            vertices that intersects all cycles of\n            <jats:italic>G<\/jats:italic>\n            (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent testbed for many important algorithmic techniques in the field such as Iterative Compression\u00a0[Guo et\u00a0al. (JCSS\u201906)], Randomized Branching\u00a0[Becker et\u00a0al. (J. Artif. Intell. Res\u201900)] and Cut&amp;Count\u00a0[Cygan et\u00a0al. (FOCS\u201911)]. In particular, there has been a long race for the smallest dependence\n            <jats:italic>f(k)<\/jats:italic>\n            in run times of the type\n            <jats:italic>\n              O\n              <jats:sup>\u22c6<\/jats:sup>\n              (f(k))\n            <\/jats:italic>\n            , where the\n            <jats:italic>\n              O\n              <jats:sup>\u22c6<\/jats:sup>\n            <\/jats:italic>\n            notation omits factors polynomial in\n            <jats:italic>n<\/jats:italic>\n            . This race seemed to have reached a conclusion in 2011, when a randomized\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>\u22c6<\/jats:sup>\n            (3\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) time algorithm based on Cut&amp;Count was introduced.\n          <\/jats:p>\n          <jats:p>\n            In this work, we show the contrary and give a\n            <jats:italic>\n              O\n              <jats:sup>\u22c6<\/jats:sup>\n              (2.7\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:italic>\n            time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size\n            <jats:italic>k<\/jats:italic>\n            of bounded average degree, a tree decomposition of width\n            <jats:italic>(1-\u03a9 (1))k<\/jats:italic>\n            can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from\u00a0[Becker et\u00a0al. (J. Artif. Intell. Res\u201900)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.\n          <\/jats:p>","DOI":"10.1145\/3504027","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T18:59:39Z","timestamp":1644865179000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Detecting Feedback Vertex Sets of Size\n            <i>k<\/i>\n            in\n            <i>O<\/i>\n            <sup>\u22c6<\/sup>\n            (2.7\n            <i>k<\/i>\n            ) Time"],"prefix":"10.1145","volume":"18","author":[{"given":"Jason","family":"Li","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburg, Kansas"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63480"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.2"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.638"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000049"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2018.1"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9904-6"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24318-4_4"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Marek Cygan Fedor Fomin Bart M. P. Jansen Lukasz Kowalik Daniel Lokshtanov Daniel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2014. Open Problems for FPT School 2014. (2014). Retrieved from http:\/\/fptschool.mimuw.edu.pl\/opl.pdf. Accessed on 17 June 2022.","DOI":"10.1007\/978-3-319-21275-3_2"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Marek Cygan Jesper Nederlof Marcin Pilipczuk Michal Pilipczuk Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. CoRR arxiv:1103.0534. Retrieved from http:\/\/arxiv.org\/abs\/1103.0534.","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90046-3"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.30"},{"key":"e_1_3_2_19_2","first-page":"191","volume-title":"Proceedings of the Complexity Theory: Current Research, Dagstuhl Workshop","author":"Downey Rodney G.","year":"1992","unstructured":"Rodney G. Downey and Michael R. Fellows. 1992. Fixed parameter tractability and completeness. In Proceedings of the Complexity Theory: Current Research, Dagstuhl Workshop. 191\u2013225."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897551"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_3_2_23_2","unstructured":"Anupam Gupta Euiwoong Lee Jason Li Pasin Manurangsi and Michal Wlodarczyk. 2018. Losing treewidth by separating subsets. CoRR arxiv:1804.01366. Retreived from http:\/\/arxiv.org\/abs\/1804.01366."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_29"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28639-4_21"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.109"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.27"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_22"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3159"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3504027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3504027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:45:05Z","timestamp":1750268705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3504027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3504027"],"URL":"https:\/\/doi.org\/10.1145\/3504027","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-01-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}