{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:57:51Z","timestamp":1780372671946,"version":"3.54.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031826696","type":"print"},{"value":"9783031826702","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_3","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:39:34Z","timestamp":1738816774000},"page":"23-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of\u00a0Feedback Vertex Set with\u00a0Connectivity Constraints"],"prefix":"10.1007","author":[{"given":"Ankit","family":"Abhinav","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satyabrata","family":"Jana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nidhi","family":"Purohit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"3_CR1","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.) IPEC 2016, Aarhus, Denmark, vol. 63 of LIPIcs, pp. 2:1\u20132:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.2","DOI":"10.4230\/LIPIcs.IPEC.2016.2"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Jain, P., Kanesh, L., Lokshtanov, D., Saurabh, S.: Conflict free feedback vertex set: a parameterized dichotomy. In: Potapov, I., Spirakis, Worrell, J. (eds.) MFCS 2018, vol. 117 of LIPIcs, pp. 53:1\u201353:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.53","DOI":"10.4230\/LIPIcs.MFCS.2018.53"},{"key":"3_CR3","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):18:1\u201318:25 (2018). https:\/\/doi.org\/10.1145\/3265027","DOI":"10.1145\/3265027"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/100789403","volume":"26","author":"O Amini","year":"2012","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting subgraphs via homomorphisms. SIAM J. Disc. Math. 26(2), 695\u2013717 (2012). https:\/\/doi.org\/10.1137\/100789403","journal-title":"SIAM J. Disc. Math."},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algor. 18(2), 17:1\u201317:31 (2022). https:\/\/doi.org\/10.1145\/3506707","DOI":"10.1145\/3506707"},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1007\/s00453-014-9966-5","volume":"74","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: On group feedback vertex set parameterized by the size of the cutset. Algorithmica 74(2), 630\u2013642 (2016). https:\/\/doi.org\/10.1007\/s00453-014-9966-5","journal-title":"Algorithmica"},{"key":"3_CR7","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory: Current Research, Dagstuhl Workshop, 2\u20138 February 1992, pp. 191\u2013225. Cambridge University Press, Cambridge (1992)"},{"key":"3_CR8","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"8","key":"3_CR9","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":"8","key":"3_CR10","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"},{"key":"3_CR11","doi-asserted-by":"publisher","unstructured":"Jana, S., Lokshtanov, D., Mandal, S., Rai, A., Saurabh, S.: Parameterized approximation scheme for feedback vertex set. In: Leroux, J., Lombardy, S., Peleg, D. (eds.) 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, France, 28 August\u20131 September 2023, vol. 272 of LIPIcs, pp. 56:1\u201356:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2023.56","DOI":"10.4230\/LIPIcs.MFCS.2023.56"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, 20\u201322 March 1972, The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/11917496_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J Kneis","year":"2006","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Divide-and-Color. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 58\u201367. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11917496_6"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Li, J., Nederlof, J.: Detecting feedback vertex sets of size k in O$$^*$$ (2.7k) time. ACM Trans. Algor. 18(4), 34:1\u201334:26 (2022). https:\/\/doi.org\/10.1145\/3504027","DOI":"10.1145\/3504027"},{"issue":"8","key":"3_CR15","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":"3_CR16","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. ACM Trans. Algor. 14(1), 7:1\u20137:37 (2018). https:\/\/doi.org\/10.1145\/3155299","DOI":"10.1145\/3155299"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2012.02.012","volume":"461","author":"N Misra","year":"2012","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized independent feedback vertex set. Theor. Comput. Sci. 461, 65\u201375 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.012","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"3_CR18","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. Comb. Optim. 24(2), 131\u2013146 (2012). https:\/\/doi.org\/10.1007\/s10878-011-9394-2","journal-title":"J. Comb. Optim."},{"issue":"3","key":"3_CR19","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 Trans. Algor. 2(3), 403\u2013415 (2006). https:\/\/doi.org\/10.1145\/1159892.1159898","journal-title":"ACM Trans. Algor."},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. xiii. The disjoint paths problem. J. Comb. Theory B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Comb. Theory B"},{"issue":"2","key":"3_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory B 92(2), 325\u2013357 (2004). https:\/\/doi.org\/10.1016\/j.jctb.2004.08.001","journal-title":"J. Comb. Theory B"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Thomass\u00e9, S: A 4k$$ ^{\\text{2}}$$ kernel for feedback vertex set. ACM Trans. Algor. 6(2), 32:1\u201332:8 (2010). https:\/\/doi.org\/10.1145\/1721837.1721848","DOI":"10.1145\/1721837.1721848"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T15:26:04Z","timestamp":1754407564000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}