{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:53:44Z","timestamp":1787320424103,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>The classical Feedback Vertex Set problem asks, for a given undirected graph $G$ and an integer $k$, to find a set of at most $k$ vertices that hits all the cycles in the graph $G$. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (Subset-FVS), where an instance comes additionally with a set $S \\subseteq V$ of vertices, and we ask for a set of at most $k$ vertices that hits all simple cycles passing through $S$. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225--267; SIAM J. Comput., 30 (2000), pp. 1231--1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by $|S|$. Next we present an algorithm which reduces the given instance to $2^k n^{O(1)}$ instances with the size of $S$ bounded by $O(k^3)$, using kernelization techniques such as the $2$-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a $2^{O(k\\log k)} n^{O(1)}$ time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable.<\/jats:p>","DOI":"10.1137\/110843071","type":"journal-article","created":{"date-parts":[[2013,2,11]],"date-time":"2013-02-11T10:38:07Z","timestamp":1360579087000},"page":"290-309","source":"Crossref","is-referenced-by-count":47,"title":["Subset Feedback Vertex Set Is Fixed-Parameter Tractable"],"prefix":"10.1137","volume":"27","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,2,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.638"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000049"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9234-2"},{"key":"atypb4","first-page":"459","author":"Bousquet N.","year":"2011","journal-title":"New York"},{"key":"atypb5","first-page":"192","author":"Burrage K.","year":"2006","journal-title":"Berlin"},{"key":"atypb6","first-page":"93","author":"Cao Y.","year":"2010","journal-title":"Berlin"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"atypb9","first-page":"150","author":"Cygan M.","year":"2011","journal-title":"Washington, DC"},{"key":"atypb10","first-page":"449","author":"Cygan M.","year":"2011","journal-title":"Berlin"},{"key":"atypb11","first-page":"1","author":"Cygan M.","year":"2011","journal-title":"Berlin"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"atypb13","first-page":"09511","author":"Demaine E. D.","year":"2010","journal-title":"Germany"},{"key":"atypb14","first-page":"191","author":"Downey R. G.","year":"1992","journal-title":"UK"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,<i>Parameterized Complexity<\/i> Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195291874"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340047"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066678"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"atypb22","first-page":"235","author":"Kanj I. A.","year":"2004","journal-title":"Berlin"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.12.001"},{"key":"atypb24","first-page":"450","author":"Kratsch S.","year":"2012","journal-title":"Washington, DC"},{"key":"atypb25","first-page":"94","author":"Kratsch S.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb26","first-page":"760","author":"Lokshtanov D.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb28","first-page":"469","author":"Marx D.","year":"2011","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2029"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110843071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:49Z","timestamp":1787317009000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110843071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110843071"],"URL":"https:\/\/doi.org\/10.1137\/110843071","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}