{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:21Z","timestamp":1750693401475},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_38","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"449-461","source":"Crossref","is-referenced-by-count":10,"title":["Subset Feedback Vertex Set Is Fixed-Parameter Tractable"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res (JAIR)\u00a012, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"1","key":"38_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci.\u00a05(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"38_CR3","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00224-009-9234-2","volume":"46","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst.\u00a046(3), 566\u2013597 (2010)","journal-title":"Theory Comput. Syst."},{"key":"38_CR4","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Proc. of STOC 2011 (to appear, 2011)"},{"key":"38_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K. Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 192\u2013202. Springer, Heidelberg (2006)"},{"key":"38_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"7","key":"38_CR7","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proc. of STOC 2008, pp. 177\u2013186 (2008)","DOI":"10.1145\/1374376.1374404"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR abs\/1103.0534 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"38_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/11533719_87","volume-title":"Computing and Combinatorics","author":"F.K.H.A. Dehne","year":"2005","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 $^{\\mbox{{o}(k)}}$ n $^{\\mbox{3}}$ ) FPT algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 859\u2013869. Springer, Heidelberg (2005)"},{"key":"38_CR11","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Marx, D.: Open problems from dagstuhl seminar 09511 (2009)"},{"key":"38_CR12","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)"},{"key":"38_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica\u00a020(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"issue":"2","key":"38_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/S0895480195291874","volume":"13","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math.\u00a013(2), 255\u2013267 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"38_CR16","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput.\u00a030(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"key":"38_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-79723-4_13","volume-title":"Parameterized and Exact Computation","author":"S. Guillemot","year":"2008","unstructured":"Guillemot, S.: FPT algorithms for path-transversals and cycle-transversals problems in graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 129\u2013140. Springer, Heidelberg (2008)"},{"issue":"8","key":"38_CR18","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci.\u00a072(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-28639-4_21","volume-title":"Parameterized and Exact Computation","author":"I.A. Kanj","year":"2004","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 235\u2013247. Springer, Heidelberg (2004)"},{"key":"38_CR20","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem (2010) (manuscript)"},{"issue":"3","key":"38_CR21","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR22","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proc. of STOC 2011 (to appear, 2011)","DOI":"10.1145\/1993636.1993699"},{"key":"38_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/3-540-36136-7_22","volume-title":"Algorithms and Computation","author":"V. Raman","year":"2002","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 241\u2013248. Springer, Heidelberg (2002)"},{"issue":"3","key":"38_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1159892.1159898","volume":"2","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms\u00a02(3), 403\u2013415 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"38_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"38_CR26","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proc. of SODA 2009, pp. 115\u2013119 (2009)","DOI":"10.1137\/1.9781611973068.13"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T21:47:54Z","timestamp":1560289674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}