{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:23Z","timestamp":1772119403596,"version":"3.50.1"},"reference-count":74,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2025,5]]},"DOI":"10.1007\/s00453-025-01293-0","type":"journal-article","created":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T09:18:03Z","timestamp":1738142283000},"page":"621-660","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Bounds for Chordal\/Interval Vertex Deletion Parameterized by Treewidth"],"prefix":"10.1007","volume":"87","author":[{"given":"Micha\u0142","family":"W\u0142odarczyk","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,29]]},"reference":[{"key":"1293_CR1","doi-asserted-by":"publisher","unstructured":"W\u0142odarczyk, M. (2023): Tight bounds for chordal\/interval vertex deletion parameterized by treewidth. In: Etessami, K., Feige, U., Puppis, G. (eds.) 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany. LIPIcs, vol. 261, pp. 106\u2013110620. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.106","DOI":"10.4230\/LIPIcs.ICALP.2023.106"},{"key":"1293_CR2","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S. (2015).: Parameterized Algorithms. Springer, Switzerland. Doi 10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"1293_CR3","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"key":"1293_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Encyclopedia of mathematics and its applications,","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. In: Encyclopedia of mathematics and its applications,. Cambridge University Press, UK (2012). https:\/\/doi.org\/10.1017\/CBO9780511977619"},{"issue":"3","key":"1293_CR5","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J. 51(3), 292\u2013302 (2008). https:\/\/doi.org\/10.1093\/comjnl\/bxm033","journal-title":"Comput. J."},{"key":"1293_CR6","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Lokshtanov, D., Saurabh, S.: A near-optimal planarization algorithm. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 1802\u20131811. SIAM, USA (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.130","DOI":"10.1137\/1.9781611973402.130"},{"key":"1293_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-030-42071-0_10","volume-title":"Treewidth Kernels and Algorithms - Essays Dedicated to Hans L Bodlaender on the Occasion of His 60th Birthday Lecture Notes in Computer Science","author":"D Marx","year":"2020","unstructured":"Marx, D.: Four shorts stories on surprising algorithmic uses of treewidth. In: Fomin, F.V., Kratsch, S., Leeuwen, E.J. (eds.) Treewidth Kernels and Algorithms - Essays Dedicated to Hans L Bodlaender on the Occasion of His 60th Birthday Lecture Notes in Computer Science, pp. 129\u2013144. Springer, Switzerland (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_10"},{"issue":"4","key":"1293_CR8","doi-asserted-by":"publisher","first-page":"30","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\u201313035 (2013). https:\/\/doi.org\/10.1145\/2500119","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1293_CR9","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, Series B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Comb. Theory, Series B"},{"issue":"4","key":"1293_CR10","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). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"1293_CR11","doi-asserted-by":"publisher","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., Van Rooij, J.M.M., Wojtaszczyk, J.O. (2022): Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms 18(2) https:\/\/doi.org\/10.1145\/3506707","DOI":"10.1145\/3506707"},{"key":"1293_CR12","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-22993-0_47","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M Pilipczuk","year":"2011","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: A logical approach. In: Murlak, F., Sankowski, P. (eds.) Mathematical Foundations of Computer Science 2011, pp. 520\u2013531. Springer, Berlin Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22993-0_47"},{"key":"1293_CR13","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). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"issue":"4","key":"1293_CR14","doi-asserted-by":"publisher","first-page":"29","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), 29\u201312960 (2016). https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"issue":"3","key":"1293_CR15","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). https:\/\/doi.org\/10.1137\/16M1104834","journal-title":"SIAM J. Comput."},{"key":"1293_CR16","doi-asserted-by":"publisher","unstructured":"Curticapea, R., Lindzey, N., Nederlof, J.: A tight lower bound for counting hamiltonian cycles via matrix rank. In: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1080\u20131099 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.70","DOI":"10.1137\/1.9781611975031.70"},{"issue":"3","key":"1293_CR17","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/3148227","volume":"65","author":"M Cygan","year":"2018","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast hamiltonicity checking via bases of perfect matchings. J. ACM 65(3), 12\u201311246 (2018). https:\/\/doi.org\/10.1145\/3148227","journal-title":"J. ACM"},{"issue":"2","key":"1293_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3170442","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), 1\u201330 (2018). https:\/\/doi.org\/10.1145\/3170442","journal-title":"ACM Trans. Algorithms"},{"key":"1293_CR19","doi-asserted-by":"publisher","unstructured":"Van\u00a0Rooij, J.M., Bodlaender, H.L., Rossmanith, P.(2009): Dynamic programming on tree decompositions using generalised fast subset convolution. In: European Symposium on Algorithms, pp. 566\u2013577. Springer, Germany . https:\/\/doi.org\/10.1007\/978-3-642-04128-0_51","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"1293_CR20","doi-asserted-by":"publisher","unstructured":"Bergougnoux, B., Bonnet, \u00c9., Brettell, N., Kwon, O.-j.: Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 180, pp. 3\u20131317 (2020).https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.3","DOI":"10.4230\/LIPIcs.IPEC.2020.3"},{"key":"1293_CR21","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.dam.2016.05.019","volume":"231","author":"M Pilipczuk","year":"2017","unstructured":"Pilipczuk, M.: A tight lower bound for vertex planarization on graphs of bounded treewidth. Discret. Appl. Math. 231, 211\u2013216 (2017). https:\/\/doi.org\/10.1016\/j.dam.2016.05.019","journal-title":"Discret. Appl. Math."},{"key":"1293_CR22","doi-asserted-by":"publisher","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 951\u2013970. SIAM, USA (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.57","DOI":"10.1137\/1.9781611975994.57"},{"issue":"3","key":"1293_CR23","doi-asserted-by":"publisher","first-page":"1623","DOI":"10.1137\/19M1287146","volume":"34","author":"J Baste","year":"2020","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: Hitting minors on bounded treewidth graphs. I. general upper bounds. SIAM J. Discret. Math. 34(3), 1623\u20131648 (2020). https:\/\/doi.org\/10.1137\/19M1287146","journal-title":"SIAM J. Discret. Math."},{"key":"1293_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2020.01.026","volume":"814","author":"J Baste","year":"2020","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: Hitting minors on bounded treewidth graphs. II. single-exponential algorithms. Theor. Comput. Sci. 814, 135\u2013152 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.01.026","journal-title":"Theor. Comput. Sci."},{"key":"1293_CR25","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.jcss.2019.11.002","volume":"109","author":"J Baste","year":"2020","unstructured":"Baste, J., Sau, I., Thilikos, D.M.: Hitting minors on bounded treewidth graphs. III. lower bounds. J. Comput. Syst. Sci. 109, 56\u201377 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2019.11.002","journal-title":"J. Comput. Syst. Sci."},{"key":"1293_CR26","doi-asserted-by":"publisher","unstructured":"Bonamy, M., Kowalik, L., Nederlof, J., Pilipczuk, M., Socala, A., Wrochna, M.: On directed feedback vertex set parameterized by treewidth. In: Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K. (eds.) Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11159, pp. 65\u201378. Springer, Germany (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_6","DOI":"10.1007\/978-3-030-00256-5_6"},{"key":"1293_CR27","doi-asserted-by":"publisher","unstructured":"Jacob, H., Bellitto, T., Defrain, O., Pilipczuk, M.: Close Relatives (Of Feedback Vertex Set), Revisited. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 214, pp. 21\u201312115. Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2021.21","DOI":"10.4230\/LIPIcs.IPEC.2021.21"},{"key":"1293_CR28","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.ic.2017.04.009","volume":"256","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256, 62\u201382 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.04.009","journal-title":"Inf. Comput."},{"key":"1293_CR29","doi-asserted-by":"publisher","unstructured":"Sau, I., Santos\u00a0Souza, U.: Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. In: Esparza, J., Kr\u00e1\u013e, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, pp. 82\u201318215. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.82","DOI":"10.4230\/LIPIcs.MFCS.2020.82"},{"issue":"5","key":"1293_CR30","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001). https:\/\/doi.org\/10.1145\/502102.502107","journal-title":"J. ACM"},{"key":"1293_CR31","doi-asserted-by":"crossref","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences of the United States of America 45(11), 1607\u20131620 (1959)","DOI":"10.1073\/pnas.45.11.1607"},{"issue":"3","key":"1293_CR32","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Discrete Math. 9(3), 205\u2013212 (1974). https:\/\/doi.org\/10.1016\/0012-365X(74)90002-8","journal-title":"Discrete Math."},{"issue":"3","key":"1293_CR33","doi-asserted-by":"publisher","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"D Kendall","year":"1969","unstructured":"Kendall, D.: Incidence matrices, interval graphs and seriation in archeology. Pac. J. Math. 28(3), 565\u2013570 (1969)","journal-title":"Pac. J. Math."},{"issue":"6","key":"1293_CR34","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389\u20131401 (1957). https:\/\/doi.org\/10.1002\/j.1538-7305.1957.tb01515.x","journal-title":"Bell Syst. Tech. J."},{"key":"1293_CR35","doi-asserted-by":"crossref","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Graph Theory and Computing, pp. 183\u2013217. Elsevier, USA (1972)","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"issue":"2","key":"1293_CR36","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"LM Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Discrete Math. 55(2), 181\u2013184 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90046-9","journal-title":"Discrete Math."},{"issue":"3","key":"1293_CR37","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127(3), 415\u2013429 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00242-1","journal-title":"Discrete Appl. Math."},{"key":"1293_CR38","doi-asserted-by":"publisher","unstructured":"Jacob, A., Panolan, F., Raman, V., Sahlot, V.: Structural parameterizations with modulator oblivion. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference). LIPIcs, vol. 180, pp. 19\u201311918. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.19","DOI":"10.4230\/LIPIcs.IPEC.2020.19"},{"issue":"4","key":"1293_CR39","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90050-X","journal-title":"Inf. Process. Lett."},{"key":"1293_CR40","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Kroon, J.J.H., W\u0142odarczyk, M.: Vertex deletion parameterized by elimination distance and even less. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021, pp. 1757\u20131769. Association for Computing Machinery, New York, NY, USA (2021). https:\/\/doi.org\/10.1145\/3406325.3451068","DOI":"10.1145\/3406325.3451068"},{"key":"1293_CR41","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201921, pp. 522\u2013539. Society for Industrial and Applied Mathematics, USA (2021). https:\/\/doi.org\/10.5555\/3458064.3458096","DOI":"10.5555\/3458064.3458096"},{"issue":"3","key":"1293_CR42","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3039243","volume":"13","author":"FV Fomin","year":"2017","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative families of product families. ACM Trans. Algorithms 13(3), 36\u201313629 (2017). https:\/\/doi.org\/10.1145\/3039243","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1293_CR43","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 $$c^k n$$ 5-approximation algorithm for treewidth. SIAM J. Computing 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Computing"},{"key":"1293_CR44","doi-asserted-by":"publisher","unstructured":"Saitoh, T., Yoshinaka, R., Bodlaender, H.L. (2021): Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes. In: Uehara, R., Hong, S., Nandy, S.C. (Eds.) WALCOM: Algorithms and Computation - 15th International Conference and Workshops, 2021, Yangon, Myanmar. Lecture Notes in Computer Science, vol. 12635, pp. 142\u2013153. Springer, Germany, https:\/\/doi.org\/10.1007\/978-3-030-68211-8_12","DOI":"10.1007\/978-3-030-68211-8_12"},{"key":"1293_CR45","doi-asserted-by":"publisher","unstructured":"Cao, Y.: Linear recognition of almost interval graphs. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1096\u20131115. SIAM, USA (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch77","DOI":"10.1137\/1.9781611974331.ch77"},{"issue":"3","key":"1293_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629595","volume":"11","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms 11(3), 1\u201335 (2015). https:\/\/doi.org\/10.1145\/2629595","journal-title":"ACM Trans. Algorithms"},{"key":"1293_CR47","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2012.03.013","volume":"511","author":"P Heggernes","year":"2013","unstructured":"Heggernes, P., van \u2019t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.: Parameterized complexity of vertex deletion into perfect graph classes. Theoretical Comput. Sci. 511, 172\u2013180 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.013","journal-title":"Theoretical Comput. Sci."},{"issue":"3","key":"1293_CR48","doi-asserted-by":"publisher","first-page":"2258","DOI":"10.1137\/17M112035X","volume":"32","author":"BMP Jansen","year":"2018","unstructured":"Jansen, B.M.P., Pilipczuk, M.: Approximation and kernelization for chordal vertex deletion. SIAM J. Discret. Math. 32(3), 2258\u20132301 (2018). https:\/\/doi.org\/10.1137\/17M112035X","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"1293_CR49","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00453-015-0054-2","volume":"76","author":"I Bliznets","year":"2016","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Largest chordal and interval subgraphs faster than $$2^n$$. Algorithmica 76(2), 569\u2013594 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"1293_CR50","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/3284356","volume":"15","author":"A Agrawal","year":"2019","unstructured":"Agrawal, A., Lokshtanov, D., Misra, P., Saurabh, S., Zehavi, M.: Feedback vertex set inspired kernel for chordal vertex deletion. ACM Trans. Algorithms 15(1), 11\u201311128 (2019). https:\/\/doi.org\/10.1145\/3284356","journal-title":"ACM Trans. Algorithms"},{"key":"1293_CR51","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Misra, P., Saurabh, S., Zehavi, M.: Interval vertex deletion admits a polynomial kernel. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201919, pp. 1711\u20131730. Society for Industrial and Applied Mathematics, USA (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.103","DOI":"10.1137\/1.9781611975482.103"},{"key":"1293_CR52","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.jctb.2020.05.002","volume":"145","author":"EJ Kim","year":"2020","unstructured":"Kim, E.J., Kwon, O.: Erd\u0151s-P\u00f3sa property of chordless cycles and its applications. J. Comb. Theory, Ser. B 145, 65\u2013112 (2020). https:\/\/doi.org\/10.1016\/j.jctb.2020.05.002","journal-title":"J. Comb. Theory, Ser. B"},{"key":"1293_CR53","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Lokshtanov, D., Misra, P., Saurabh, S., Zehavi, M.: Erd\u00f6s-P\u00f3sa property of obstructions to interval graphs. In: Niedermeier, R., Vall\u00e9e, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France. LIPIcs, vol. 96, pp. 7\u20131715. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.7","DOI":"10.4230\/LIPIcs.STACS.2018.7"},{"key":"1293_CR54","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Kolay, S., Lokshtanov, D., Saurabh, S.: A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9644, pp. 1\u201313. Springer, Germany (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_1","DOI":"10.1007\/978-3-662-49529-2_1"},{"key":"1293_CR55","doi-asserted-by":"publisher","unstructured":"Ahn, J., Eiben, E., Kwon, O.-j., Oum, S.-i.: A Polynomial Kernel for 3-Leaf Power Deletion. In: Esparza, J., Kr\u00e1\u013e, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, pp. 5\u20131514. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.5","DOI":"10.4230\/LIPIcs.MFCS.2020.5"},{"issue":"7","key":"1293_CR56","doi-asserted-by":"publisher","first-page":"2106","DOI":"10.1007\/s00453-022-00963-7","volume":"84","author":"J Ahn","year":"2022","unstructured":"Ahn, J., Kim, E.J., Lee, E.: Towards constant-factor approximation for chordal\/distance-hereditary vertex deletion. Algorithmica 84(7), 2106\u20132133 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00963-7","journal-title":"Algorithmica"},{"issue":"4","key":"1293_CR57","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00453-012-9661-3","volume":"65","author":"P Hof","year":"2013","unstructured":"Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica 65(4), 845\u2013867 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9661-3","journal-title":"Algorithmica"},{"issue":"2","key":"1293_CR58","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/3381426","volume":"16","author":"I Bliznets","year":"2020","unstructured":"Bliznets, I., Cygan, M., Komosa, P., Pilipczuk, M., Mach, L.: Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. ACM Trans. Algorithms 16(2), 25\u201312531 (2020). https:\/\/doi.org\/10.1145\/3381426","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"1293_CR59","doi-asserted-by":"publisher","first-page":"2197","DOI":"10.1137\/11085390X","volume":"42","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. SIAM J. Computing 42(6), 2197\u20132216 (2013). https:\/\/doi.org\/10.1137\/11085390X","journal-title":"SIAM J. Computing"},{"key":"1293_CR60","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: On the hardness of eliminating small induced subgraphs by contracting edges. In: Gutin, G.Z., Szeider, S. (eds.) Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8246, pp. 243\u2013254. Springer, Germany (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_21","DOI":"10.1007\/978-3-319-03898-8_21"},{"issue":"1","key":"1293_CR61","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77\u201379 (1981). https:\/\/doi.org\/10.1137\/0602010","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"1293_CR62","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.jcss.2015.11.008","volume":"82","author":"H Shachnai","year":"2016","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488\u2013502 (2016). https:\/\/doi.org\/10.1016\/j.jcss.2015.11.008","journal-title":"J. Comput. Syst. Sci."},{"key":"1293_CR63","doi-asserted-by":"publisher","unstructured":"Zehavi, M. (2015) : Mixing color coding-related techniques. In: Algorithms-ESA 2015, pp. 1037\u20131049. Springer, Germany https:\/\/doi.org\/10.1007\/978-3-662-48350-3_86","DOI":"10.1007\/978-3-662-48350-3_86"},{"issue":"5","key":"1293_CR64","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. J. ACM 63(5), 44\u201314469 (2016). https:\/\/doi.org\/10.1145\/2973749","journal-title":"J. ACM"},{"key":"1293_CR65","unstructured":"Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs, 1st edn. Prentice Hall PTR, USA (1998). https:\/\/dl.acm.org\/doi\/10.5555\/551884"},{"key":"1293_CR66","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O.-j., Marx, D.: Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In: Lokshtanov, D., Nishimura, N. (eds.) 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 89, pp. 7\u20131713. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.7","DOI":"10.4230\/LIPIcs.IPEC.2017.7"},{"issue":"1","key":"1293_CR67","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Series B 16(1), 47\u201356 (1974). https:\/\/doi.org\/10.1016\/0095-8956(74)90094-X","journal-title":"J. Comb. Theory, Series B"},{"key":"1293_CR68","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer, New York, NY (1993)"},{"key":"1293_CR69","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. Soc. Ind. Appl. Math. Philadelphia, PA, USA (1999). https:\/\/doi.org\/10.1137\/1.9780898719796","journal-title":"Soc. Ind. Appl. Math. Philadelphia, PA, USA"},{"key":"1293_CR70","volume-title":"Treewidth, Computations and Approximations. Lecture Notes in Computer Science","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Germany (1994)"},{"key":"1293_CR71","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, USA (2006)"},{"issue":"2","key":"1293_CR72","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s00453-018-0489-3","volume":"81","author":"M W\u0142odarczyk","year":"2019","unstructured":"W\u0142odarczyk, M.: Clifford algebras meet tree decompositions. Algorithmica 81(2), 497\u2013518 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0489-3","journal-title":"Algorithmica"},{"key":"1293_CR73","unstructured":"Jansen, B.M.P., Kroon, J.J.H., W\u0142odarczyk, M.: Vertex deletion parameterized by elimination distance and even less. CoRR abs\/2103.09715 (2021) arxiv:2103.09715v4"},{"issue":"1","key":"1293_CR74","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-015-0014-x","volume":"75","author":"Y Cao","year":"2016","unstructured":"Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. Algorithmica 75(1), 118\u2013137 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0014-x","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01293-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01293-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01293-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T07:01:17Z","timestamp":1746687677000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01293-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,29]]},"references-count":74,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1293"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01293-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3389260\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,29]]},"assertion":[{"value":"26 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}