{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T01:46:25Z","timestamp":1780105585138,"version":"3.54.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER award 1053605"},{"name":"ONR YIP award N000141110662"},{"name":"Graduate Student International Research Fellowship from the University of Maryland and a Simons Award for Graduate Students in Theoretical Computer Science"},{"name":"NCN","award":["N206567140"],"award-info":[{"award-number":["N206567140"]}]},{"name":"DARPA\/AFRL award FA8650-11-1-7162"},{"name":"Foundation for Polish Science"},{"name":"OTKA","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}]},{"name":"University of Maryland Research and Scholarship Award (RASA)"},{"name":"ERC Starting","award":["NEWNET 279352"],"award-info":[{"award-number":["NEWNET 279352"]}]},{"name":"ERC Starting","award":["PARAMTIGHT (No. 280152)"],"award-info":[{"award-number":["PARAMTIGHT (No. 280152)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>Given a graph<jats:italic>G<\/jats:italic>and an integer<jats:italic>k<\/jats:italic>, the<jats:sc>Feedback Vertex Set<\/jats:sc>(FVS) problem asks if there is a vertex set<jats:italic>T<\/jats:italic>of size at most<jats:italic>k<\/jats:italic>that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC \u201908, JACM \u201908) showed that it is fixed-parameter tractable by giving a 4<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup><jats:italic>k<\/jats:italic>! \u00b7<jats:italic>n<\/jats:italic><jats:sup><jats:italic>O<\/jats:italic>(1)<\/jats:sup>time algorithm. There are two subset versions of this problems: We are given an additional subset<jats:italic>S<\/jats:italic>of vertices (resp., edges), and we want to hit all cycles passing through a vertex of<jats:italic>S<\/jats:italic>(resp., an edge of<jats:italic>S<\/jats:italic>); the two variants are known to be equivalent in the parameterized sense. Recently, the<jats:sc>Subset<\/jats:sc>FVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP\u201911, SIDMA\u201913) and independently by Kakimura et al. (SODA \u201912). We generalize the result of Chen et al. (STOC \u201908, JACM \u201908) by showing that a<jats:sc>Subset<\/jats:sc>FVS in directed graphs can be solved in time 2<jats:sup><jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic><jats:sup>3<\/jats:sup>)<\/jats:sup>\u010b<jats:italic>n<\/jats:italic><jats:sup><jats:italic>O<\/jats:italic>(1)<\/jats:sup>(i.e., FPT parameterized by size<jats:italic>k<\/jats:italic>of the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC \u201911, SICOMP \u201914) to show that<jats:sc>Undirected Multicut<\/jats:sc>is FPT, and it was generalized by Chitnis et al. (SODA \u201912, SICOMP \u201913) to directed graphs to show that<jats:sc>Directed Multiway Cut<\/jats:sc>is FPT. In addition to proving the FPT of a<jats:sc>Directed Subset<\/jats:sc>FVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from 2<jats:sup>2<jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>)<\/jats:sup>to 2<jats:sup><jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup>)<\/jats:sup>in the parameter dependence of the<jats:sc>Directed Multiway Cut<\/jats:sc>algorithm of Chitnis et al. (SODA \u201912, SICOMP \u201913).<\/jats:p>","DOI":"10.1145\/2700209","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable"],"prefix":"10.1145","volume":"11","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland, Warszawa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammataghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622248.1622256"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Hans L. Bodlaender. 1991. On disjoint cycles. In WG. 230--238. Hans L. Bodlaender. 1991. On disjoint cycles. In WG. 230--238.","DOI":"10.1007\/3-540-55121-2_24"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Paul Bonsma and Daniel Lokshtanov. 2011. Feedback vertex set in mixed graphs. In WADS. 122--133. Paul Bonsma and Daniel Lokshtanov. 2011. Feedback vertex set in mixed graphs. In WADS. 122--133.","DOI":"10.1007\/978-3-642-22300-6_11"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_20"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Rajesh Hemant Chitnis Fedor V. Fomin Daniel Lokshtanov Pranabendu Misra M. S. Ramanujan and Saket Saurabh. 2013a. Faster exact algorithms for some terminal set problems. In IPEC. 150--162. Rajesh Hemant Chitnis Fedor V. Fomin Daniel Lokshtanov Pranabendu Misra M. S. Ramanujan and Saket Saurabh. 2013a. Faster exact algorithms for some terminal set problems. In IPEC. 150--162.","DOI":"10.1007\/978-3-319-03898-8_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594439"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_1_18_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer-Verlag . 530 pp. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer-Verlag. 530 pp."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Guy Even Joseph Naor Baruch Schieber and Madhu Sudan. 1995. Approximating minimum feedback sets and multi-cuts in directed graphs. In IPCO. 14--28. Guy Even Joseph Naor Baruch Schieber and Madhu Sudan. 1995. Approximating minimum feedback sets and multi-cuts in directed graphs. In IPCO. 14--28.","DOI":"10.1007\/3-540-59408-6_38"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340047"},{"key":"e_1_2_1_21_1","volume-title":"Parameterized Complexity Theory","author":"Flum Jorge","unstructured":"Jorge Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag . 493 pp. Jorge Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag. 493 pp."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.11.012"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Falk H\u00fcffner Christian Komusiewicz Hannes Moser and Rolf Niedermeier. 2008. Fixed-parameter algorithms for cluster vertex deletion. In LATIN. 711--722. Falk H\u00fcffner Christian Komusiewicz Hannes Moser and Rolf Niedermeier. 2008. Fixed-parameter algorithms for cluster vertex deletion. In LATIN. 711--722.","DOI":"10.1007\/978-3-540-78773-0_61"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Naonori Kakimura Kenichi 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 Kenichi 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_26_1","doi-asserted-by":"crossref","unstructured":"Iyad A. Kanj Michael J. Pelsmajer and Marcus Schaefer. 2004. Parameterized algorithms for feedback vertex set. In IWPEC. 235--247. Iyad A. Kanj Michael J. Pelsmajer and Marcus Schaefer. 2004. Parameterized algorithms for feedback vertex set. In IWPEC. 235--247.","DOI":"10.1007\/978-3-540-28639-4_21"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_49"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_63"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_36_1","volume-title":"Data Structures and Algorithms 2: Graph Algorithms and NP-completeness","author":"Mehlhorn Kurt","unstructured":"Kurt Mehlhorn . 1984. Data Structures and Algorithms 2: Graph Algorithms and NP-completeness . Springer . Kurt Mehlhorn. 1984. Data Structures and Algorithms 2: Graph Algorithms and NP-completeness. Springer."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Moni Naor Leonard J. Schulman and Aravind Srinivasan. 1995. Splitters and near-optimal derandomization. In FOCS. 182--191. Moni Naor Leonard J. Schulman and Aravind Srinivasan. 1995. Splitters and near-optimal derandomization. In FOCS. 182--191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"e_1_2_1_38_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Venkatesh Raman Saket Saurabh and C. R. Subramanian. 2002. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In ISAAC. 241--248. Venkatesh Raman Saket Saurabh and C. R. Subramanian. 2002. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In ISAAC. 241--248.","DOI":"10.1007\/3-540-36136-7_22"},{"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":"crossref","unstructured":"Igor Razgon. 2007. Computing minimum directed feedback vertex set in O(1.9977n). In ICTCS. 70--81. Igor Razgon. 2007. Computing minimum directed feedback vertex set in O(1.9977 n ). In ICTCS. 70--81.","DOI":"10.1142\/9789812770998_0010"},{"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.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:43Z","timestamp":1750223263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2700209"],"URL":"https:\/\/doi.org\/10.1145\/2700209","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}