{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T19:37:03Z","timestamp":1780342623094,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,25]],"date-time":"2014-12-25T00:00:00Z","timestamp":1419465600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-014-9966-5","type":"journal-article","created":{"date-parts":[[2014,12,24]],"date-time":"2014-12-24T11:37:43Z","timestamp":1419421063000},"page":"630-642","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["On Group Feedback Vertex Set Parameterized by the Size of the Cutset"],"prefix":"10.1007","volume":"74","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"family":"Marcin Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"family":"Micha\u0142 Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,12,25]]},"reference":[{"key":"9966_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) 12, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"1","key":"9966_CR2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9966_CR3","first-page":"93","volume-title":"SWAT, Lecture Notes in Computer Science","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, Lecture Notes in Computer Science, vol. 6139, pp. 93\u2013104. Springer, Berlin (2010)"},{"issue":"7","key":"9966_CR4","doi-asserted-by":"crossref","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. 74(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9966_CR5","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. J. ACM 55(5), 1\u201319 (2008)","DOI":"10.1145\/1411509.1411511"},{"issue":"5","key":"9966_CR6","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00493-006-0030-1","volume":"26","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Geelen, J., Gerards, B., Goddyn, L.A., Lohman, M., Seymour, P.D.: Packing non-zero A-paths in group-labelled graphs. Combinatorica 26(5), 521\u2013532 (2006)","journal-title":"Combinatorica"},{"key":"9966_CR7","doi-asserted-by":"crossref","unstructured":"Cygan M, Nederlof J, Pilipczuk M, Pilipczuk M, van Rooij JMM, Wojtaszczyk JO (2011) Solving connectivity problems parameterized by treewidth in single exponential time. In Ostrovsky R (ed) FOCS, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"9966_CR8","first-page":"194","volume-title":"WG, Lecture Notes in Computer Science","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: On group feedback vertex set parameterized by the size of the cutset. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG, Lecture Notes in Computer Science, vol. 7551, pp. 194\u2013205. Springer, Berlin (2012)"},{"issue":"1","key":"9966_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1), 3 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"9966_CR10","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9966_CR11","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"FKHA Dehne","year":"2007","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An $${O}(2^{o(k)}) {n}^{3}$$ O ( 2 o ( k ) ) n 3 FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9966_CR12","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, Dagstuhl Workshop, pp. 191\u2013225 (1992)"},{"key":"9966_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"1","key":"9966_CR14","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discret. Optim. 8(1), 61\u201371 (2011)","journal-title":"Discret. Optim."},{"issue":"8","key":"9966_CR15","doi-asserted-by":"crossref","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. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9966_CR16","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K., Yoshida, Y.: Linear-time FPT algorithms via network flow. In: Chekuri, C. (ed.) SODA, pp. 1749\u20131761. SIAM (2014)","DOI":"10.1137\/1.9781611973402.127"},{"key":"9966_CR17","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching and FPT algorithms. CoRR abs\/1310.2841v2 (2014)","DOI":"10.1137\/1.9781611973402.128"},{"key":"9966_CR18","first-page":"235","volume-title":"IWPEC, Lecture Notes in Computer Science","author":"IA 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.K.H.A. (eds.) IWPEC, Lecture Notes in Computer Science, vol. 3162, pp. 235\u2013247. Springer, Berlin (2004)"},{"issue":"2","key":"9966_CR19","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.jctb.2005.08.001","volume":"96","author":"K Kawarabayashi","year":"2006","unstructured":"Kawarabayashi, K., Wollan, P.: Non-zero disjoint cycles in highly connected group labelled graphs. J. Comb. Theory Ser. B 96(2), 296\u2013301 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9966_CR20","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: FOCS, pp. 450\u2013459. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"3","key":"9966_CR21","doi-asserted-by":"crossref","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. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9966_CR22","unstructured":"Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: LP can be a cure for parameterized problems. In: D\u00fcrr, C., Wilke, T. (eds.) STACS, LIPIcs, vol. 14, pp. 338\u2013349. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"issue":"3","key":"9966_CR23","doi-asserted-by":"crossref","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 Trans. Algorithms 2(3), 403\u2013415 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"8","key":"9966_CR24","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9966_CR25","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9966_CR26","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A $$4k^2$$ 4 k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9966_CR27","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, LP-branching and FPT algorithms. In: Chekuri, C. (ed.) SODA, pp. 1762\u20131781. SIAM (2014)","DOI":"10.1137\/1.9781611973402.128"},{"issue":"1","key":"9966_CR28","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s00493-011-2551-5","volume":"31","author":"P Wollan","year":"2011","unstructured":"Wollan, P.: Packing cycles with modularity constraints. Combinatorica 31(1), 95\u2013126 (2011)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9966-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9966-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9966-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T20:27:53Z","timestamp":1566160073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9966-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,25]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9966"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9966-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,25]]}}}