{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T01:53:29Z","timestamp":1768787609151,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T00:00:00Z","timestamp":1588118400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T00:00:00Z","timestamp":1588118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2016-258"],"award-info":[{"award-number":["RPG-2016-258"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph is<jats:italic>H<\/jats:italic>-free if it contains no induced subgraph isomorphic to\u00a0<jats:italic>H<\/jats:italic>. We prove new complexity results for the two classical cycle transversal problems<jats:sc>Feedback Vertex Set<\/jats:sc>and<jats:sc>Odd Cycle Transversal<\/jats:sc>by showing that they can be solved in polynomial time on<jats:inline-formula><jats:alternatives><jats:tex-math>$$(sP_1+ P_3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>s<\/mml:mi><mml:msub><mml:mi>P<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><mml:mo>+<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mn>3<\/mml:mn><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs for every integer<jats:inline-formula><jats:alternatives><jats:tex-math>$$s\\ge 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>s<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show the same result for the variants<jats:sc>Connected Feedback Vertex Set<\/jats:sc>and<jats:sc>Connected Odd Cycle Transversal<\/jats:sc>. We also prove that the latter two problems are polynomial-time solvable on cographs; this was already known for<jats:sc>Feedback Vertex Set<\/jats:sc>and<jats:sc>Odd Cycle Transversal<\/jats:sc>. We complement these results by proving that<jats:sc>Odd Cycle Transversal<\/jats:sc>and<jats:sc>Connected Odd Cycle Transversal<\/jats:sc>are -complete on<jats:inline-formula><jats:alternatives><jats:tex-math>$$(P_2+ P_5,P_6)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msub><mml:mo>+<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mn>5<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mn>6<\/mml:mn><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs.<\/jats:p>","DOI":"10.1007\/s00453-020-00706-6","type":"journal-article","created":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T02:02:34Z","timestamp":1588125754000},"page":"2841-2866","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9515-6945","authenticated-orcid":false,"given":"Konrad K.","family":"Dabrowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-7213","authenticated-orcid":false,"given":"Carl","family":"Feghali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7295-2663","authenticated-orcid":false,"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2383-1339","authenticated-orcid":false,"given":"Giacomo","family":"Paesani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,29]]},"reference":[{"issue":"2","key":"706_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"},{"key":"706_CR2","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.dam.2016.08.011","volume":"217","author":"R Belmonte","year":"2017","unstructured":"Belmonte, R., van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D.: The price of connectivity for feedback vertex set. Discrete Appl. Math. 217, 132\u2013143 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"706_CR3","doi-asserted-by":"publisher","first-page":"1342","DOI":"10.1007\/s00453-018-0474-x","volume":"81","author":"M Bonamy","year":"2019","unstructured":"Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex set for $$P_5$$-free graphs. Algorithmica 81(4), 1342\u20131369 (2019)","journal-title":"Algorithmica"},{"key":"706_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the restriction of some NP-complete graph problems to permutation graphs. In: Proceedings of FCT 1985, LNCS, vol. 199, pp. 53\u201362 (1985)","DOI":"10.1007\/BFb0028791"},{"key":"706_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey, volume 3 of SIAM Monographs on Discrete Mathematics and Applications","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, volume 3 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"issue":"1","key":"706_CR6","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s00373-018-1981-x","volume":"35","author":"E Camby","year":"2019","unstructured":"Camby, E.: Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs. Graphs Comb. 35(1), 103\u2013118 (2019)","journal-title":"Graphs Comb."},{"issue":"1","key":"706_CR7","first-page":"207","volume":"16","author":"E Camby","year":"2014","unstructured":"Camby, E., Cardinal, J., Fiorini, S., Schaudt, O.: The price of connectivity for vertex cover. Discrete Math. Theor. Comput. Sci. 16(1), 207\u2013224 (2014)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"706_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2014.05.029","volume":"177","author":"E Camby","year":"2014","unstructured":"Camby, E., Schaudt, O.: The price of connectivity for dominating set: upper bounds and complexity. Discrete Appl. Math. 177, 53\u201359 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"26\u201328","key":"706_CR9","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/j.tcs.2010.03.021","volume":"411","author":"J Cardinal","year":"2010","unstructured":"Cardinal, J., Levy, E.: Connected vertex covers in dense graphs. Theor. Comput. Sci. 411(26\u201328), 2581\u20132590 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"706_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2017.09.033","volume":"705","author":"N Chiarelli","year":"2018","unstructured":"Chiarelli, N., Hartinger, T.R., Johnson, M., Milani\u010d, M., Paulusma, D.: Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Theor. Comput. Sci. 705, 75\u201383 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"706_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, 1st edn. Springer, Berlin (2015)","edition":"1"},{"issue":"1","key":"706_CR12","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B Escoffier","year":"2010","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algorithms 8(1), 36\u201349 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"706_CR13","doi-asserted-by":"crossref","unstructured":"Feghali, C., Johnson, M., Paesani, G., Paulusma, D.: On cycle transversals and their connected variants in the absence of a small linear forest. In: Proceedings of FCT 2019, LNCS vol. 11651, pp. 258\u2013273 (2019)","DOI":"10.1007\/978-3-030-25027-0_18"},{"issue":"2","key":"706_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: complexity and algorithms. J. Discrete Algorithms 7(2), 149\u2013167 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"706_CR15","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"706_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"706_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory 84(4), 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"key":"706_CR18","doi-asserted-by":"crossref","unstructured":"Grigoriev, A., Sitters, R.: Connected feedback vertex set in planar graphs. In: Proceedings of WG 2009, LNCS, vol. 5911, pp. 143\u2013153 (2010)","DOI":"10.1007\/978-3-642-11409-0_13"},{"key":"706_CR19","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.dam.2019.04.010","volume":"267","author":"C Groenland","year":"2019","unstructured":"Groenland, C., Okrasa, K., Rz\u0105\u017cewski, P., Scott, A.D., Seymour, P.D., Spirkl, S.T.: $$H$$-colouring $$P_t$$-free graphs in subexponential time. Discrete Appl. Math. 267, 184\u2013189 (2019)","journal-title":"Discrete Appl. Math."},{"key":"706_CR20","first-page":"1257","volume":"2019","author":"A Grzesik","year":"2019","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$P_6$$-free graphs. Proc. SODA 2019, 1257\u20131271 (2019)","journal-title":"Proc. SODA"},{"key":"706_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.ejc.2016.06.003","volume":"58","author":"TR Hartinger","year":"2016","unstructured":"Hartinger, T.R., Johnson, M., Milani\u010d, M., Paulusma, D.: The price of connectivity for cycle transversals. Eur. J. Comb. 58, 203\u2013224 (2016)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"706_CR22","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"706_CR23","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":"1","key":"706_CR24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00453-019-00601-9","volume":"82","author":"M Johnson","year":"2020","unstructured":"Johnson, M., Paesani, G., Paulusma, D.: Connected vertex cover for $$(sP_1+P_5)$$-free graphs. Algorithmica 82(1), 20\u201340 (2020)","journal-title":"Algorithmica"},{"issue":"3","key":"706_CR25","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"706_CR26","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)","journal-title":"Theor. Comput. Sci."},{"key":"706_CR27","doi-asserted-by":"publisher","first-page":"387","DOI":"10.7151\/dmgt.1598","volume":"32","author":"R Mosca","year":"2012","unstructured":"Mosca, R.: Stable sets for $$(P_6, K_{2,3})$$-free graphs. Discussiones Mathematicae Graph Theory 32, 387\u2013401 (2012)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"706_CR28","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2017.06.012","volume":"692","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: Boundary classes for graph problems involving non-local properties. Theor. Comput. Sci. 692, 46\u201371 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"706_CR29","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jcss.2019.12.004","volume":"109","author":"K Okrasa","year":"2020","unstructured":"Okrasa, K., Rz\u0105\u017cewski, P.: Subexponential algorithms for variants of the homomorphism problem in string graphs. J. Comput. Syst. Sci. 109, 126\u2013144 (2020)","journal-title":"J. Comput. Syst. Sci."},{"key":"706_CR30","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15, 307\u2013309 (1974)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"issue":"1","key":"706_CR31","first-page":"51","volume":"2","author":"PLK Priyadarsini","year":"2008","unstructured":"Priyadarsini, P.L.K., Hemalatha, T.: Connected vertex cover in 2-connected planar graph with maximum degree 4 is NP-complete. Int. J. Math. Phys. Eng. Sci. 2(1), 51\u201354 (2008)","journal-title":"Int. J. Math. Phys. Eng. Sci."},{"issue":"1","key":"706_CR32","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Math. 29(1), 53\u201376 (1980)","journal-title":"Discrete Math."},{"key":"706_CR33","unstructured":"Speckenmeyer, E.: Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. Ph.D. thesis, Universit\u00e4t Paderborn (1983)"},{"issue":"3","key":"706_CR34","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"706_CR35","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."},{"key":"706_CR36","doi-asserted-by":"crossref","unstructured":"Watanabe, T., Kajita, S., Onaga, K.: Vertex covers and connected vertex covers in 3-connected graphs. In: Proceedings of IEEE International Sympoisum on Circuits and Systems 1991, vol. 2, pp. 1017\u20131020 (1991)","DOI":"10.1109\/ISCAS.1991.176537"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00706-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00706-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00706-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T22:00:12Z","timestamp":1722808812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00706-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,29]]},"references-count":36,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["706"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00706-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,29]]},"assertion":[{"value":"5 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}