{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:40Z","timestamp":1759638820024,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T00:00:00Z","timestamp":1519603200000},"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":[[2018,9]]},"DOI":"10.1007\/s00453-018-0419-4","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T11:06:09Z","timestamp":1519643169000},"page":"2683-2724","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"first","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,26]]},"reference":[{"issue":"2","key":"419_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230190206","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas, E., Yu, C.S.: On graphs with polynomially solvable maximum-weight clique problem. Networks 19(2), 247\u2013253 (1989)","journal-title":"Networks"},{"issue":"3","key":"419_CR2","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00224-009-9234-2","volume":"46","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566\u2013597 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"35","key":"419_CR3","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"419_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"419_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"419_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"419_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-014-9904-6","volume":"73","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: new measure and new structures. Algorithmica 73(1), 63\u201386 (2015)","journal-title":"Algorithmica"},{"key":"419_CR8","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., Rooij, J., Wojtaszczyk, J.O.: Solving Connectivity Problems Parameterized by Treewidth in Singly Exponential Time. In: IEEE 52nd annual symposium on foundations of computer science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, pp. 150\u2013159 (2011)"},{"key":"419_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"},{"issue":"5\u20136","key":"419_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.ipl.2013.01.001","volume":"113","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M.: Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5\u20136), 179\u2013182 (2013)","journal-title":"Inf. Process. Lett."},{"key":"419_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"4","key":"419_CR12","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)","journal-title":"J. ACM"},{"key":"419_CR13","series-title":"Graduate texts in mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate texts in mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"419_CR14","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"3","key":"419_CR15","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"key":"419_CR16","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"419_CR17","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In: IEEE symposium of foundations of computer science FOCS, pp. 470\u2013479 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"419_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F., Str\u00f8mme, T.: Vertex cover structural parameterization revisited. In: Graph-Theoretic Concepts in Computer Science\u201442nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, pp. 171\u2013182 (2016)","DOI":"10.1007\/978-3-662-53536-3_15"},{"issue":"4","key":"419_CR19","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","journal-title":"J. ACM"},{"issue":"1","key":"419_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"419_CR21","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","volume":"86","author":"T Fujito","year":"1998","unstructured":"Fujito, T.: A unified approximation algorithm for node-deletion problems. Discrete Appl. Math. 86(2\u20133), 213\u2013231 (1998)","journal-title":"Discrete Appl. Math."},{"key":"419_CR22","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H Freeman, San Francisco (1979)"},{"issue":"2","key":"419_CR23","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402\u2013410 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"419_CR24","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"419_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-012-9393-4","volume":"53","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited\u2014upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"key":"419_CR26","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70\u201388 (2013)","journal-title":"Inf. Comput."},{"issue":"4","key":"419_CR27","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TST.2014.6867520","volume":"19","author":"BMP Jansen","year":"2014","unstructured":"Jansen, B.M.P., Raman, V., Vatshelle, M.: Parameter ecology for feedback vertex set. Tsinghua Sci. Technol. 19(4), 387\u2013409 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"419_CR28","unstructured":"Kloks, T., Liu, C., Poon, S.: Feedback vertex set on chordal bipartite graphs. CoRR abs\/1104.3915v2 (2011)"},{"issue":"10","key":"419_CR29","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)","journal-title":"Inf. Process. Lett."},{"key":"419_CR30","unstructured":"Kolay, S., Panolan, F.: Parameterized Algorithms for Deletion to (r, l)-Graphs. In: Proceedings of foundation of software technology and theoretical computer science FSTTCS, pp. 420\u2013433 (2015)"},{"issue":"10","key":"419_CR31","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discrete Appl. Math. 156(10), 1936\u20131947 (2008)","journal-title":"Discrete Appl. Math."},{"key":"419_CR32","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Kernels for Structural Parameterizations of Vertex Cover\u2014Case of Small Degree Modulators. In: 10th international symposium of parameterized and exact computation IPEC, pp. 331\u2013342 (2015)"},{"key":"419_CR33","doi-asserted-by":"crossref","unstructured":"Majumdar, D., Raman, V.: FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters. In: International Frontiers of Algorithmics Workshop FAW, pp. 209\u2013220 (2017)","DOI":"10.1007\/978-3-319-59605-1_19"},{"key":"419_CR34","unstructured":"Majumdar, D.: Structural Parameterizations of Feedback Vertex Set. In: 11th international symposium of parameterized and exact computation IPEC, pp. 21:1\u201321:16 (2016)"},{"issue":"3","key":"419_CR35","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00453-007-9112-8","volume":"53","author":"R Rizzi","year":"2009","unstructured":"Rizzi, R.: Minimum weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402\u2013424 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"419_CR36","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A 4k $${}^{\\text{2 }}$$ 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"1\u20133","key":"419_CR37","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Math. 72(1\u20133), 355\u2013360 (1988)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0419-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0419-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0419-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T17:54:13Z","timestamp":1570816453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0419-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,26]]},"references-count":37,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["419"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0419-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,2,26]]},"assertion":[{"value":"30 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}