{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:15Z","timestamp":1740109335298,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,1,27]],"date-time":"2024-01-27T00:00:00Z","timestamp":1706313600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,27]],"date-time":"2024-01-27T00:00:00Z","timestamp":1706313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s00453-023-01206-z","type":"journal-article","created":{"date-parts":[[2024,1,27]],"date-time":"2024-01-27T20:02:11Z","timestamp":1706385731000},"page":"1657-1699","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved FPT Algorithms for Deletion to Forest-Like Structures"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6573-9445","authenticated-orcid":false,"given":"Kishen N.","family":"Gowda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aditya","family":"Lonkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vraj","family":"Patel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,27]]},"reference":[{"key":"1206_CR1","doi-asserted-by":"publisher","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: In: Du, D.-Z., Pardalos, P.M. (eds.) Feedback Set Problems, pp. 209\u2013258. Springer, Boston, MA (1999). https:\/\/doi.org\/10.1007\/978-1-4757-3023-4_4","DOI":"10.1007\/978-1-4757-3023-4_4"},{"key":"1206_CR2","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: On disjoint cycles. In: Schmidt, G., Berghammer, R. (eds.) Graph-Theoretic Concepts in Computer Science, pp. 230\u2013238. Springer, Berlin, (1992). https:\/\/doi.org\/10.1007\/3-540-55121-2_24","DOI":"10.1007\/3-540-55121-2_24"},{"key":"1206_CR3","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J.B. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user Boston, Boston, MA (1995). https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_7","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"1206_CR4","doi-asserted-by":"publisher","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) Algorithms and Computation, pp. 241\u2013248. Springer, Berlin, (2002). https:\/\/doi.org\/10.1007\/3-540-36136-7_22","DOI":"10.1007\/3-540-36136-7_22"},{"issue":"3","key":"1206_CR5","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/11533719_87","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 $${\\cal{O} }(2^{{\\cal{O} }(k)} n^{3})$$ FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479\u2013492 (2007). https:\/\/doi.org\/10.1007\/11533719_87","journal-title":"Theory Comput. Syst."},{"issue":"8","key":"1206_CR6","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. 72(8), 1386\u20131396 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.02.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1206_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.5555\/1622248.1622256","volume":"12","author":"A Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Int. Res. 12(1), 219\u2013234 (2000). https:\/\/doi.org\/10.5555\/1622248.1622256","journal-title":"J. Artif. Int. Res."},{"key":"1206_CR8","doi-asserted-by":"publisher","unstructured":"Cao, Y.: A naive algorithm for feedback vertex set. In: Seidel, R. (ed.) 1st Symposium on simplicity in algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), vol. 61, pp. 1\u2013119. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.1","DOI":"10.4230\/OASIcs.SOSA.2018.1"},{"issue":"1","key":"1206_CR9","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). https:\/\/doi.org\/10.1007\/s00453-014-9904-6","journal-title":"Algorithmica"},{"issue":"7","key":"1206_CR10","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. 74(7), 1188\u20131198 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2008.05.002","journal-title":"J. Comput. Syst. Sci."},{"key":"1206_CR11","doi-asserted-by":"publisher","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., Rooij, J.M.M.v., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 150\u2013159 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.23","DOI":"10.1109\/FOCS.2011.23"},{"issue":"8","key":"1206_CR12","doi-asserted-by":"publisher","first-page":"2503","DOI":"10.1007\/s00453-021-00815-w","volume":"83","author":"Y Iwata","year":"2021","unstructured":"Iwata, Y., Kobayashi, Y.: Improved analysis of highest-degree branching for feedback vertex set. Algorithmica 83(8), 2503\u20132520 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00815-w","journal-title":"Algorithmica"},{"issue":"10","key":"1206_CR13","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":"1206_CR14","doi-asserted-by":"publisher","unstructured":"Li, J., Nederlof, J.: Detecting feedback vertex sets of size $$k$$ in $${O}^\\star (2.7^k)$$ time. ACM Trans. Algorithms 18(4) (2022) https:\/\/doi.org\/10.1145\/3504027","DOI":"10.1145\/3504027"},{"issue":"2","key":"1206_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s10878-011-9394-2","volume":"24","author":"N Misra","year":"2012","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms for connected feedback vertex set. J. Combinat. Opt. 24(2), 131\u2013146 (2012). https:\/\/doi.org\/10.1007\/s10878-011-9394-2","journal-title":"J. Combinat. Opt."},{"key":"1206_CR16","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Gupta, S., Saurabh, S., Sharma, R.: Improved algorithms and combinatorial bounds for independent feedback vertex set. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 63, pp. 2\u20131214. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.2","DOI":"10.4230\/LIPIcs.IPEC.2016.2"},{"issue":"8","key":"1206_CR17","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1007\/s00224-020-09973-w","volume":"64","author":"S Li","year":"2020","unstructured":"Li, S., Pilipczuk, M.: An improved FPT algorithm for independent feedback vertex set. Theory Comput. Syst. 64(8), 1317\u20131330 (2020). https:\/\/doi.org\/10.1007\/s00224-020-09973-w","journal-title":"Theory Comput. Syst."},{"key":"1206_CR18","doi-asserted-by":"publisher","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized independent feedback vertex set. Theor. Comput. Sci. 461, 65\u201375 (2012). 17th International Computing and Combinatorics Conference (COCOON 2011). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.012 .","DOI":"10.1016\/j.tcs.2012.02.012"},{"key":"1206_CR19","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Lokshtanov, D., Mouawad, A.E., Saurabh, S.: Simultaneous feedback vertex set: A parameterized perspective. ACM Trans. Comput. Theory 10(4) (2018) https:\/\/doi.org\/10.1145\/3265027","DOI":"10.1145\/3265027"},{"key":"1206_CR20","unstructured":"Ye, J.: A note on finding dual feedback vertex set. CoRR abs\/1510.00773 (2015) arXiv:1510.00773"},{"issue":"1","key":"1206_CR21","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. Disc. Math. 27(1), 290\u2013309 (2013). https:\/\/doi.org\/10.1137\/110843071","journal-title":"SIAM J. Disc. Math."},{"issue":"4","key":"1206_CR22","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016). https:\/\/doi.org\/10.1137\/140962838","journal-title":"SIAM J. Comput."},{"key":"1206_CR23","doi-asserted-by":"publisher","unstructured":"Iwata, Y., Yamaguchi, Y., Yoshida, Y.: 0\/1\/all CSPs, half-integral A-path packing, and linear-time FPT algorithms. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 462\u2013473. IEEE Computer Society, Los Alamitos, CA, USA (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00051","DOI":"10.1109\/FOCS.2018.00051"},{"issue":"4","key":"1206_CR24","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jctb.2011.12.001","volume":"102","author":"K-I Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K.-I., 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"},{"key":"1206_CR25","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. ACM Trans. Algorithms 14(1) (2018) https:\/\/doi.org\/10.1145\/3155299","DOI":"10.1145\/3155299"},{"key":"1206_CR26","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Ono, H., Otachi, Y.: A faster parameterized algorithm for pseudoforest deletion. Discret. Appl. Math. 236, 42\u201356 (2018) https:\/\/doi.org\/10.1016\/j.dam.2017.10.018","DOI":"10.1016\/j.dam.2017.10.018"},{"issue":"2","key":"1206_CR27","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/16M1100794","volume":"32","author":"G Philip","year":"2018","unstructured":"Philip, G., Rai, A., Saurabh, S.: Generalized pseudoforest deletion: Algorithms and uniform kernel. SIAM J. Discret. Math. 32(2), 882\u2013901 (2018). https:\/\/doi.org\/10.1137\/16M1100794","journal-title":"SIAM J. Discret. Math."},{"key":"1206_CR28","doi-asserted-by":"publisher","unstructured":"Rai, A., Saurabh, S.: Bivariate complexity analysis of almost forest deletion. Theor. Comput. Sci. 708, 18\u201333 (2018) https:\/\/doi.org\/10.1016\/j.tcs.2017.10.021","DOI":"10.1016\/j.tcs.2017.10.021"},{"key":"1206_CR29","doi-asserted-by":"publisher","unstructured":"Lin, M., Feng, Q., Wang, J., Chen, J., Fu, B., Li, W.: An improved FPT algorithm for almost forest deletion problem. Inf. Process. Lett. 136, 30\u201336 (2018) https:\/\/doi.org\/10.1016\/j.ipl.2018.03.016","DOI":"10.1016\/j.ipl.2018.03.016"},{"issue":"1","key":"1206_CR30","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/bf02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987). https:\/\/doi.org\/10.1007\/bf02579206","journal-title":"Combinatorica"},{"key":"1206_CR31","doi-asserted-by":"publisher","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. ISSAC \u201914, pp. 296\u2013303. Association for Computing Machinery, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"key":"1206_CR32","doi-asserted-by":"publisher","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discrete Math. 23, 407\u2013427 (2009) https:\/\/doi.org\/10.1137\/080715482","DOI":"10.1137\/080715482"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01206-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01206-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01206-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:03:34Z","timestamp":1713668614000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01206-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,27]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1206"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01206-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,1,27]]},"assertion":[{"value":"24 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}