{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:07Z","timestamp":1759639087293,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030489656"},{"type":"electronic","value":"9783030489663"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-3-030-48966-3_18","type":"book-chapter","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T13:04:23Z","timestamp":1590671063000},"page":"237-250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Singly Connected Vertex Deletion"],"prefix":"10.1007","author":[{"given":"Avinandan","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawqueen","family":"Kanesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayakrishnan","family":"Madathil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Komal","family":"Muluk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nidhi","family":"Purohit","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":[[2020,5,29]]},"reference":[{"issue":"7","key":"18_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jcss.2017.07.008","volume":"92","author":"A Agrawal","year":"2018","unstructured":"Agrawal, A., Saurabh, S., Sharma, R., Zehavi, M.: Kernels for deletion to classes of acyclic digraphs. J. Comput. Syst. Sci. 92, 9\u201321 (2018)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"18_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"18_CR4","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1002\/jgt.3190140310","volume":"14","author":"J Bang-Jensen","year":"1990","unstructured":"Bang-Jensen, J.: Locally semicomplete digraphs: a generalization of tournaments. J. Graph Theory 14(3), 371\u2013390 (1990)","journal-title":"J. Graph Theory"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J.: Locally semicomplete digraphs and generalizations. In: Classes of Directed Graphs, pp. 245\u2013296 (2018)","DOI":"10.1007\/978-3-319-71840-8_6"},{"key":"18_CR6","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71840-8","volume-title":"Classes of Directed Graphs","year":"2018","unstructured":"Bang-Jensen, J., Gutin, G. (eds.): Classes of Directed Graphs. SMM. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-71840-8"},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-015-0038-2","volume":"76","author":"J Bang-Jensen","year":"2016","unstructured":"Bang-Jensen, J., Maddaloni, A., Saurabh, S.: Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica 76(2), 320\u2013343 (2016)","journal-title":"Algorithmica"},{"issue":"4","key":"18_CR8","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","unstructured":"Bergougnoux, B., Eiben, E., Ganian, R., Ordyniak, S., Ramanujan, M.S.: Towards a polynomial kernel for directed feedback vertex set. In: MFCS, pp. 36:1\u201336:15 (2017)"},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","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."},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0020-0190(93)90261-7","volume":"48","author":"AL Buchsbaum","year":"1993","unstructured":"Buchsbaum, A.L., Carlisle, M.C.: Determining uni-connectivity in directed graphs. Inf. Process. Lett. 48(1), 9\u201312 (1993)","journal-title":"Inf. Process. Lett."},{"key":"18_CR12","unstructured":"Cao, Y.: A naive algorithm for feedback vertex set. In: SOSA, pp. 1:1\u20131:9 (2018)"},{"issue":"1","key":"18_CR13","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"},{"issue":"7","key":"18_CR14","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"18_CR15","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","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), 21:1\u201321:19 (2008)","journal-title":"J. ACM"},{"issue":"4\u20135","key":"18_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"FA Chudak","year":"1998","unstructured":"Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4\u20135), 111\u2013118 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"18_CR17","doi-asserted-by":"publisher","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$${}^{\\text{ o(k) }}$$n$${}^{\\text{3 }}$$) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"18_CR18","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"issue":"9","key":"18_CR19","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1016\/j.ipl.2015.04.008","volume":"115","author":"M Dietzfelbinger","year":"2015","unstructured":"Dietzfelbinger, M., Jaberi, R.: On testing single connectedness in directed graphs and some related problems. Inf. Process. Lett. 115(9), 684\u2013688 (2015)","journal-title":"Inf. Process. Lett."},{"key":"18_CR20","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pp. 36\u201349 (1992)"},{"key":"18_CR21","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)"},{"issue":"4","key":"18_CR22","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jctb.2014.07.002","volume":"110","author":"A Fradkin","year":"2015","unstructured":"Fradkin, A., Seymour, P.: Edge-disjoint paths in digraphs with bounded independence number. J. Comb. Theory Ser. B 110, 19\u201346 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"18_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(96)00094-4","volume":"59","author":"T Fujito","year":"1996","unstructured":"Fujito, T.: A note on approximation of the vertex cover and feedback vertex set problems - unified approach. Inf. Process. Lett. 59(2), 59\u201363 (1996)","journal-title":"Inf. Process. Lett."},{"key":"18_CR25","unstructured":"Gallai, T., Milgram, A.N.: Verallgemeinerung eines graphentheoretischen satzes von r\u00e9dei: Ladislaus r\u00e9dei zum 60. geburtstag. Acta scientiarum mathematicarum 21(3\u20134), 181\u2013186 (1960)"},{"issue":"8","key":"18_CR26","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: IWPEC, pp. 235\u2013247 (2004)","DOI":"10.1007\/978-3-540-28639-4_21"},{"key":"18_CR28","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"3\u20134","key":"18_CR29","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0020-0190(99)00135-0","volume":"72","author":"S Khuller","year":"1999","unstructured":"Khuller, S.: An o($$\\vert $$v$$\\vert $$$${}^{\\text{2 }}$$) algorithm for single connectedness. Inf. Process. Lett. 72(3\u20134), 105\u2013107 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"5\u20136","key":"18_CR30","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0020-0190(00)00054-5","volume":"74","author":"S Khuller","year":"2000","unstructured":"Khuller, S.: Addendum to \u201can o($$\\vert $$v$$\\vert $$$${}^{\\text{2 }}$$) algorithm for single connectedness\u201d. Inf. Process. Lett. 74(5\u20136), 263 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"18_CR31","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."},{"issue":"4","key":"18_CR32","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0252-9602(17)30520-9","volume":"19","author":"D Li","year":"1999","unstructured":"Li, D., Liu, Y.: A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph 1. Acta Mathematica Scientia 19(4), 375\u2013381 (1999)","journal-title":"Acta Mathematica Scientia"},{"issue":"3","key":"18_CR33","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)00133-2","volume":"52","author":"YD Liang","year":"1994","unstructured":"Liang, Y.D.: On the feedback vertex set problem in permutation graphs. Inf. Process. Lett. 52(3), 123\u2013129 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"18_CR34","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"YD Liang","year":"1997","unstructured":"Liang, Y.D., Chang, M.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34(5), 337\u2013346 (1997)","journal-title":"Acta Informatica"},{"key":"18_CR35","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Sharma, R., Zehavi, M.: Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS. In: WADS, pp. 523\u2013537 (2019)","DOI":"10.1007\/978-3-030-24766-9_38"},{"key":"18_CR36","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","volume":"25","author":"M Mnich","year":"2017","unstructured":"Mnich, M., van Leeuwen, E.J.: Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim. 25, 48\u201376 (2017)","journal-title":"Discrete Optim."},{"issue":"3","key":"18_CR37","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. Algorithms 2(3), 403\u2013415 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"18_CR38","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)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"18_CR39","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"PD Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15(2), 281\u2013288 (1995)","journal-title":"Combinatorica"},{"issue":"2","key":"18_CR40","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 4$$k^{2}$$ kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"18_CR41","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Department of Computer and Information Science, Link\u00f6pings universitet (2007)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-48966-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T15:16:52Z","timestamp":1710256612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-48966-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030489656","9783030489663"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-48966-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"29 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bordeaux","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2020.labri.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,8","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5,9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference had to be postponed due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}