{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T12:10:19Z","timestamp":1754482219918,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152","280152"],"award-info":[{"award-number":["280152","280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152","280152"],"award-info":[{"award-number":["280152","280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2018R1D1A1B07050294"],"award-info":[{"award-number":["NRF-2018R1D1A1B07050294"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-019-00579-4","type":"journal-article","created":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T08:04:47Z","timestamp":1556179487000},"page":"3890-3935","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms"],"prefix":"10.1007","volume":"81","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1136-418X","authenticated-orcid":false,"given":"Nick","family":"Brettell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,25]]},"reference":[{"key":"579_CR1","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth. In: 12th International Symposium on Parameterized and Exact Computation, volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 4:1\u20134:12 (2018)"},{"key":"579_CR2","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: A complexity dichotomy for hitting small planar minors parameterized by treewidth. In: 13th International Symposium on Parameterized and Exact Computation, volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 2:1\u20132:13 (2019)"},{"key":"579_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"579_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A \n                    \n                      \n                    \n                    $$c^k n$$\n                    \n                      \n                        \n                          \n                            c\n                            k\n                          \n                          n\n                        \n                      \n                    \n                   5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"key":"579_CR5","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O., Marx, D.: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. In: 12th International Symposium on Parameterized and Exact Computation, volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 7:1\u20137:13 (2018)"},{"key":"579_CR6","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O., Marx, D.: Parameterized vertex deletion problems for hereditary graph classes with a block property. In: Graph-Theoretic Concepts in Computer Science, volume 9941 of Lecture Notes in Computer Science, pp. 233\u2013244 (2016)","DOI":"10.1007\/978-3-662-53536-3_20"},{"issue":"1","key":"579_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"579_CR8","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, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"579_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 52nd Annual Symposium on Foundations of Computer Science, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"4","key":"579_CR10","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s00453-016-0127-x","volume":"76","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M., van\u00a0\u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016)","journal-title":"Algorithmica"},{"key":"579_CR11","doi-asserted-by":"crossref","unstructured":"Enright, J., Meeks, K.: Deleting edges to restrict the size of an epidemic: a new application for treewidth. In: Combinatorial Optimization and Applications, volume 9486 of Lecture Notes in Computer Science, pp. 574\u2013585. Springer (2015)","DOI":"10.1007\/978-3-319-26626-8_42"},{"issue":"2","key":"579_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"issue":"4","key":"579_CR13","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 60 (2016). Art. 29","journal-title":"J. ACM"},{"key":"579_CR14","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"2","key":"579_CR15","first-page":"30","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 30 (2018). Art. 13","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"579_CR16","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"579_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00579-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00579-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00579-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T23:19:28Z","timestamp":1587683968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00579-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,25]]},"references-count":17,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["579"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00579-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,4,25]]},"assertion":[{"value":"31 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}