{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T13:57:18Z","timestamp":1779890238045,"version":"3.53.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T00:00:00Z","timestamp":1529971200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K025090"],"award-info":[{"award-number":["EP\/K025090"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000608","name":"London Mathematical Society","doi-asserted-by":"publisher","award":["41536"],"award-info":[{"award-number":["41536"]}],"id":[{"id":"10.13039\/501100000608","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"name":"Fondation Sciences Mathematiques de Paris"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0474-x","type":"journal-article","created":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T18:44:47Z","timestamp":1530038687000},"page":"1342-1369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Independent Feedback Vertex Set for $$P_5$$ P 5 -Free Graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9515-6945","authenticated-orcid":false,"given":"Konrad K.","family":"Dabrowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-7213","authenticated-orcid":false,"given":"Carl","family":"Feghali","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7295-2663","authenticated-orcid":false,"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"key":"474_CR1","unstructured":"Agrawal, A., Gupta, S., Saurabh, S., Sharma, R.: Improved algorithms and combinatorial bounds for independent feedback vertex set. In: Proceedings of IPEC 2016, LIPIcs, vol. 63, pp. 2:1\u20132:14 (2017)"},{"issue":"2","key":"474_CR2","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-Completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3(2), 73\u201376 (1980)","journal-title":"J. Inf. Process."},{"issue":"4","key":"474_CR3","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF02352694","volume":"21","author":"G Bacs\u00f3","year":"1990","unstructured":"Bacs\u00f3, G., Tuza, Zs: Dominating cliques in $$P_5$$ P 5 -free graphs. Period. Math. Hung. 21(4), 303\u2013308 (1990)","journal-title":"Period. Math. Hung."},{"key":"474_CR4","unstructured":"Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex set for $${P_5}$$ P 5 -free graphs. In: Proceedings of ISAAC 2017, LIPIcs, vol. 92, pp. 16:1\u201316:12 (2017)"},{"key":"474_CR5","unstructured":"Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Recognizing graphs close to bipartite graphs. In: Proceedings of MFCS 2017, LIPIcs, vol. 83, pp. 70:1\u201370:14 (2017)"},{"key":"474_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ipl.2017.11.004","volume":"131","author":"M Bonamy","year":"2018","unstructured":"Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex sets for graphs of bounded diameter. Inf. Process. Lett. 131, 26\u201332 (2018)","journal-title":"Inf. Process. Lett."},{"key":"474_CR7","unstructured":"Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica (in press)"},{"key":"474_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2012.10.030","volume":"469","author":"A Brandst\u00e4dt","year":"2013","unstructured":"Brandst\u00e4dt, A., Brito, S., Klein, S., Nogueira, L.T., Protti, F.: Cycle transversals in perfect graphs and cographs. Theor. Comput. Sci. 469, 15\u201323 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"474_CR9","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"},{"issue":"4","key":"474_CR10","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1007\/s00453-012-9709-4","volume":"68","author":"A Brandst\u00e4dt","year":"2014","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings for $$P_7$$ P 7 -free graphs in linear time. Algorithmica 68(4), 998\u20131018 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"474_CR11","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s00453-016-0150-y","volume":"77","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Finding dominating induced matchings in $$P_8$$ P 8 -free graphs in polynomial time. Algorithmica 77(4), 1283\u20131302 (2017)","journal-title":"Algorithmica"},{"issue":"15","key":"474_CR12","doi-asserted-by":"publisher","first-page":"3060","DOI":"10.1016\/j.dam.2008.01.021","volume":"156","author":"DM Cardoso","year":"2008","unstructured":"Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Appl. Math. 156(15), 3060\u20133065 (2008)","journal-title":"Discrete Appl. Math."},{"key":"474_CR13","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":"474_CR14","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K Edwards","year":"1986","unstructured":"Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337\u2013343 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"04","key":"474_CR15","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1017\/S0963548398003678","volume":"7","author":"T Emden-Weinert","year":"1998","unstructured":"Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7(04), 375\u2013386 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"474_CR16","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1007\/978-0-387-74759-0_178","volume-title":"Encyclopedia of Optimization","author":"P Festa","year":"2009","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 1005\u20131016. Springer, Berlin (2009)","edition":"2"},{"key":"474_CR17","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 & Co., New York (1979)"},{"issue":"7","key":"474_CR18","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard, W., Henning, M.A.: Independent domination in graphs: a survey and recent results. Discrete Math. 313(7), 839\u2013854 (2013)","journal-title":"Discrete Math."},{"key":"474_CR19","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Heggernes, P.: Choosability of $$P_5$$ P 5 -free graphs. In: Proceedings of MFCS 2009, LNCS, vol. 5734, pp. 382\u2013391 (2009)","DOI":"10.1007\/978-3-642-03816-7_33"},{"issue":"4","key":"474_CR20","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"},{"issue":"5","key":"474_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"DL Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48(5), 221\u2013228 (1993)","journal-title":"Inf. Process. Lett."},{"key":"474_CR22","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$P_6$$ P 6 -free graphs. arXiv:1707.05491 (2017)"},{"issue":"1","key":"474_CR23","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1002\/jgt.22182","volume":"88","author":"A Hertz","year":"2018","unstructured":"Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D.: Dominating induced matchings in graphs containing no long claw. J. Graph Theory 88(1), 18\u201339 (2018)","journal-title":"J. Graph Theory"},{"issue":"1","key":"474_CR24","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C.T., Kami\u0144ski, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding $$k$$ k -colorability of $$P_5$$ P 5 -free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"474_CR25","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"474_CR26","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. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"10","key":"474_CR27","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":"474_CR28","doi-asserted-by":"crossref","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Zs, Woeginger, J.G.: Complexity of coloring graphs without forbidden induced subgraphs. In: Proceedings of WG 2001, LNCS, vol. 2204, pp. 254\u2013262 (2001)","DOI":"10.1007\/3-540-45477-2_23"},{"key":"474_CR29","unstructured":"Labarre, A.: Comment on \u201ccomplexity of finding\u00a0 $$2$$ 2 vertex-disjoint $$(|V|\/2)$$ ( | V | \/ 2 ) -cycles in cubic graphs?\u201d. http:\/\/cstheory.stackexchange.com\/questions\/6107\/complexity-of-finding-$2$-vertex-disjoint-v-$2$-cycles-in-cubic-graphs (2011). Accessed 24 June 2018"},{"key":"474_CR30","doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in $$P_5$$ P 5 -free graphs in polynomial time. In: Proceedings of SODA, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"474_CR31","unstructured":"Lov\u00e1sz, L.: Coverings and coloring of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. VIII, pp. 3\u201312 (1973)."},{"issue":"1","key":"474_CR32","first-page":"61","volume":"2","author":"VV Lozin","year":"2007","unstructured":"Lozin, V.V., Kami\u0144ski, M.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2(1), 61\u201366 (2007)","journal-title":"Contrib. Discrete Math."},{"issue":"4","key":"474_CR33","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30:1\u201330:35 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"474_CR34","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":"474_CR35","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":"474_CR36","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."},{"issue":"6","key":"474_CR37","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1016\/j.disc.2017.01.006","volume":"340","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: On line graphs of subcubic triangle-free graphs. Discrete Math. 340(6), 1210\u20131226 (2017)","journal-title":"Discrete Math."},{"key":"474_CR38","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"2\u20133","key":"474_CR39","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: 3-Colorability $$\\in $$ \u2208 P for $$P_6$$ P 6 -free graphs. Discrete Appl. Math. 136(2\u20133), 299\u2013313 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"474_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs: a survey. Graphs Comb. 20(1), 1\u201340 (2004)","journal-title":"Graphs Comb."},{"issue":"1\u20133","key":"474_CR41","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0012-365X(01)00335-1","volume":"251","author":"B Randerath","year":"2002","unstructured":"Randerath, B., Schiermeyer, I., Tewes, M.: Three-colourability and forbidden subgraphs. II: polynomial algorithms. Discrete Math. 251(1\u20133), 137\u2013153 (2002)","journal-title":"Discrete Math."},{"issue":"1","key":"474_CR42","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 cardinalite maximum dans un graphe sans etoile. Discrete Math. 29(1), 53\u201376 (1980)","journal-title":"Discrete Math."},{"issue":"6","key":"474_CR43","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1587\/transfun.E98.A.1179","volume":"E98\u2013A","author":"Y Tamura","year":"2015","unstructured":"Tamura, Y., Ito, T., Zhou, X.: Algorithms for the independent feedback vertex set problem. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E98\u2013A(6), 1179\u20131188 (2015)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"12","key":"474_CR44","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1016\/j.disc.2005.09.016","volume":"306","author":"A Yang","year":"2006","unstructured":"Yang, A., Yuan, J.: Partition the vertices of a graph into one independent set and one acyclic set. Discrete Math. 306(12), 1207\u20131216 (2006)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0474-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0474-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0474-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T10:23:34Z","timestamp":1751711014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0474-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,26]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["474"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0474-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,26]]},"assertion":[{"value":"29 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}