{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T04:27:43Z","timestamp":1772684863261,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,9,11]],"date-time":"2017-09-11T00:00:00Z","timestamp":1505088000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00224-017-9805-6","type":"journal-article","created":{"date-parts":[[2017,9,11]],"date-time":"2017-09-11T12:23:20Z","timestamp":1505132600000},"page":"63-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["A Randomized Polynomial Kernel for Subset Feedback Vertex Set"],"prefix":"10.1007","volume":"62","author":[{"given":"Eva-Maria C.","family":"Hols","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,11]]},"reference":[{"key":"9805_CR1","doi-asserted-by":"publisher","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: IWPEC 2006, LNCS, vol. 4169, pp 192\u2013202. Springer (2006). http:\/\/dx.doi.org\/https:\/\/doi.org\/10.1007\/11847250_18","DOI":"10.1007\/11847250_18"},{"key":"9805_CR2","doi-asserted-by":"publisher","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. In: FOCS 2011, pp 150\u2013159. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.23","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"9805_CR3","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/110843071","journal-title":"J. Discrete Math."},{"issue":"4","key":"9805_CR4","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014). https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"key":"9805_CR5","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory (graduate texts in mathematics) (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"issue":"2","key":"9805_CR6","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. 13(2), 255\u2013267 (2000). https:\/\/doi.org\/10.1137\/S0895480195291874","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"9805_CR7","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. 30(4), 1231\u20131252 (2000). https:\/\/doi.org\/10.1137\/S0097539798340047","journal-title":"SIAM J. Comput."},{"key":"9805_CR8","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact algorithms. In: SODA 2014, pp 142\u2013151. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.10","DOI":"10.1137\/1.9781611973402.10"},{"issue":"1-2","key":"9805_CR9","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02066678","volume":"12","author":"T Gallai","year":"1961","unstructured":"Gallai, T.: Maximum-minimum s\u00e4tze und verallgemeinerte faktoren von graphen. Acta Math. Hung. 12(1-2), 131\u2013173 (1961)","journal-title":"Acta Math. Hung."},{"issue":"4","key":"9805_CR10","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jctb.2011.12.001","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem. J. Comb. Theory, Ser. B 102 (4), 1020\u20131034 (2012). https:\/\/doi.org\/10.1016\/j.jctb.2011.12.001","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"10","key":"9805_CR11","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014). https:\/\/doi.org\/10.1016\/j.ipl.2014.05.001","journal-title":"Inf. Process. Lett."},{"key":"9805_CR12","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: FOCS 2012, pp 450\u2013459. IEEE Computer Society (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.46","DOI":"10.1109\/FOCS.2012.46"},{"key":"9805_CR13","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. In: ICALP 2015, LNCS, vol. 9134, pp 935\u2013946. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_76","DOI":"10.1007\/978-3-662-47672-7_76"},{"key":"9805_CR14","unstructured":"Lov\u00e1sz, L.: Flats in matroids and geometric graphs. In: Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pp 45\u201386. Academic Press, London (1977)"},{"issue":"2","key":"9805_CR15","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. J. Comb. Theory, Ser. B 28(2), 208\u2013236 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90066-0","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"44","key":"9805_CR16","doi-asserted-by":"publisher","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.07.027","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9805_CR17","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithm. 9(4), 30 (2013). https:\/\/doi.org\/10.1145\/2500119","journal-title":"ACM Trans. Algorithm."},{"key":"9805_CR18","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0022-247X(68)90163-7","volume":"22","author":"H Perfect","year":"1968","unstructured":"Perfect, H.: Applications of Menger\u2019s graph theorem. J. Math. Anal. Appl. 22, 96\u2013111 (1968)","journal-title":"J. Math. Anal. Appl."},{"issue":"4","key":"9805_CR19","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.orl.2003.10.009","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9805_CR20","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1006\/jctb.2000.2029","volume":"82","author":"A Schrijver","year":"2001","unstructured":"Schrijver, A.: A short proof of Mader\u2019s sigma-paths theorem. J. Comb. Theory, Ser. B 82(2), 319\u2013321 (2001). https:\/\/doi.org\/10.1006\/jctb.2000.2029","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9805_CR21","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A 4k 2 kernel for feedback vertex set. ACM Trans. Algorithm. 6(2), 32:1\u201332:8 (2010). https:\/\/doi.org\/10.1145\/1721837.1721848","journal-title":"ACM Trans. Algorithm."},{"key":"9805_CR22","volume-title":"Solving the weighted parity problem for gammoids by reduction to graphic matching","author":"P Tong","year":"1982","unstructured":"Tong, P., Lawler, E.L., Vazirani, V.V.: Solving the weighted parity problem for gammoids by reduction to graphic matching. Computer Science Division University of California, USA (1982)"},{"key":"9805_CR23","doi-asserted-by":"publisher","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, lp-branching and FPT algorithms. In: SODA 2014, pp 1762\u20131781. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.128","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9805-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9805-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9805-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T05:33:48Z","timestamp":1570080828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9805-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,11]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9805"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9805-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,11]]}}}