{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T19:37:27Z","timestamp":1780342647651,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,3]],"date-time":"2018-01-03T00:00:00Z","timestamp":1514937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["BeHard"],"award-info":[{"award-number":["BeHard"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>\n            In the S\n            <jats:sc>ubset<\/jats:sc>\n            F\n            <jats:sc>eedback<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            (S\n            <jats:sc>ubset<\/jats:sc>\n            FVS) problem, the input is a graph\n            <jats:italic>G<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges, a subset of vertices\n            <jats:italic>T<\/jats:italic>\n            , referred to as terminals, and an integer\n            <jats:italic>k<\/jats:italic>\n            . The objective is to determine whether there exists a set of at most\n            <jats:italic>k<\/jats:italic>\n            vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the F\n            <jats:sc>eedback<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. Using tools from graph minors,, Kawarabayashi and Kobayashi obtained an algorithm for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS running in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\u010b\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            ) [SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS running in time 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u010b\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . More recently, Wahlstr\u00f6m obtained the first single exponential time algorithm for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS, running in time 4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            \u010b\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            [SODA 2014]. While the 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            dependence on the parameter\n            <jats:italic>k<\/jats:italic>\n            is optimal under the Exponential Time Hypothesis, the dependence of this algorithm as well as those preceding it, on the input size is at least quadratic. In this article, we design the first linear time parameterized algorithms for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS. More precisely, we obtain the following new algorithms for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS.\n          <\/jats:p>\n          <jats:p>\n            \u2014 A randomized algorithm for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS running in time\n            <jats:italic>O<\/jats:italic>\n            (25.6\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            \u010b (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            )).\n          <\/jats:p>\n          <jats:p>\n            \u2014 A deterministic algorithm for S\n            <jats:sc>ubset<\/jats:sc>\n            FVS running in time 2\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            ) \u010b (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            Since it is known that assuming the Exponential Time Hypothesis, S\n            <jats:sc>ubset<\/jats:sc>\n            FVS cannot have an algorithm running in time 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            , our first algorithm obtains the best possible asymptotic dependence on both the parameter as well as the input size. Both of our algorithms are based on \u201ccut centrality,\u201d in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.\n          <\/jats:p>","DOI":"10.1145\/3155299","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Linear Time Parameterized Algorithms for S\n            <scp>ubset<\/scp>\n            F\n            <scp>eedback<\/scp>\n            V\n            <scp>ertex<\/scp>\n            S\n            <scp>et<\/scp>"],"prefix":"10.1145","volume":"14","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of Bergen, Norway, Bergen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway, Bergen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.60"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9904-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700209"},{"key":"e_1_2_1_8_1","volume-title":"to appear","author":"Cygan Marek","year":"2014","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . to appear in 2014 . Parameterized Algorithms. Springer-Verlag , Berlin. Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. to appear in 2014. Parameterized Algorithms. Springer-Verlag, Berlin."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2010. Graph Theory ( 4 th ed.). Springer-Verlag , Heidelberg . Reinhard Diestel. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg.","edition":"4"},{"key":"e_1_2_1_12_1","unstructured":"Frederic Dorn. 2010. Planar subgraph isomorphism revisited. In STACS. 263--274.  Frederic Dorn. 2010. Planar subgraph isomorphism revisited. In STACS. 263--274."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195291874"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340047"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_16_1","volume-title":"Reed","author":"Grohe Martin","year":"2013","unstructured":"Martin Grohe , Ken-ichi Kawarabayashi, and Bruce A . Reed . 2013 . A simple algorithm for the graph minor decomposition - Logic meets structural graph theory. In SODA. 414--431. Martin Grohe, Ken-ichi Kawarabayashi, and Bruce A. Reed. 2013. A simple algorithm for the graph minor decomposition - Logic meets structural graph theory. In SODA. 414--431."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Carsten Gutwenger and Petra Mutzel. 2000. A linear time implementation of SPQR-trees. In GD. 77--90.   Carsten Gutwenger and Petra Mutzel. 2000. A linear time implementation of SPQR-trees. In GD. 77--90.","DOI":"10.1007\/3-540-44541-2_8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Yoichi Iwata Keigo Oka and Yuichi Yoshida. 2014. Linear-time FPT algorithms via network flow. In SODA. 1749--1761.   Yoichi Iwata Keigo Oka and Yuichi Yoshida. 2014. Linear-time FPT algorithms via network flow. In SODA. 1749--1761.","DOI":"10.1137\/1.9781611973402.127"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/140962838"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Bart M. P. Jansen Daniel Lokshtanov and Saket Saurabh. 2014. A near-optimal planarization algorithm. In SODA. 1802--1811.   Bart M. P. Jansen Daniel Lokshtanov and Saket Saurabh. 2014. A near-optimal planarization algorithm. In SODA. 1802--1811.","DOI":"10.1137\/1.9781611973402.130"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Naonori Kakimura Ken-ichi Kawarabayashi and Yusuke Kobayashi. 2012. Erd\u00f6s-P\u00f3sa property and its algorithmic applications: Parity constraints subset feedback set and subset packing. In SODA. 1726--1736.   Naonori Kakimura Ken-ichi Kawarabayashi and Yusuke Kobayashi. 2012. Erd\u00f6s-P\u00f3sa property and its algorithmic applications: Parity constraints subset feedback set and subset packing. In SODA. 1726--1736.","DOI":"10.1137\/1.9781611973099.137"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.45"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.12.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374443"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_2_1_31_1","volume-title":"Reed","author":"Kawarabayashi","year":"2009","unstructured":"Ken-ichi Kawarabayashi and Bruce A . Reed . 2009 . A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In SODA. 1183--1192. Ken-ichi Kawarabayashi and Bruce A. Reed. 2009. A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In SODA. 1183--1192."},{"key":"e_1_2_1_32_1","volume-title":"Reed","author":"Kawarabayashi","year":"2010","unstructured":"Ken-ichi Kawarabayashi and Bruce A . Reed . 2010 . An (almost) linear time algorithm for odd cycles transversal. In SODA. 365--378. Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In SODA. 365--378."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_63"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_37_1","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_38_1","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications , Vol. 31 . Oxford University Press , Oxford . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.05.004"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3128600"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Magnus Wahlstr\u00f6m. 2014. Half-integrality LP-branching and FPT algorithms. In SODA. 1762--1781.   Magnus Wahlstr\u00f6m. 2014. Half-integrality LP-branching and FPT algorithms. In SODA. 1762--1781.","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:28Z","timestamp":1750213588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,3]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3155299"],"URL":"https:\/\/doi.org\/10.1145\/3155299","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,3]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}