{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T15:57:43Z","timestamp":1770047863943,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T00:00:00Z","timestamp":1766448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T00:00:00Z","timestamp":1766448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"DOI":"10.1007\/s00453-025-01356-2","type":"journal-article","created":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T05:17:55Z","timestamp":1766467075000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Independent Set when Excluding an Induced Minor: $$K_1 + tK_2$$ and $$tC_3 \\uplus C_4$$"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Julien","family":"Duron","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-7634","authenticated-orcid":false,"given":"Colin","family":"Geniet","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4841-5937","authenticated-orcid":false,"given":"Alexandra","family":"Wesolek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,23]]},"reference":[{"issue":"1","key":"1356_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1751-0473-9-6","volume":"9","author":"KJ Abraham","year":"2014","unstructured":"Abraham, K.J., Diaz, C.: Identifying large sets of unrelated individuals and unrelated markers. Source Code Biol. Med. 9(1), 1\u20138 (2014)","journal-title":"Source Code Biol. Med."},{"key":"1356_CR2","doi-asserted-by":"publisher","unstructured":"Abrishami, T., Chudnovsky, M., Dibek, C., Rzazewski, P.: Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws. In Joseph\u00a0(Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 1448\u20131470. SIAM, (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.61","DOI":"10.1137\/1.9781611977073.61"},{"key":"1356_CR3","doi-asserted-by":"publisher","unstructured":"Abrishami, T., Chudnovsky, M., Pilipczuk, M., Rz\u0105\u017cewski, P., Seymour, P.D.: Induced subgraphs of bounded treewidth and the container method. In D\u00e1niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, (2021), pages 1948\u20131964. SIAM, 2021. https:\/\/doi.org\/10.1137\/1.9781611976465.116","DOI":"10.1137\/1.9781611976465.116"},{"key":"1356_CR4","unstructured":"Ahn, S., Seo, Y., Shin, J.: Learning what to defer for maximum independent sets. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 134\u2013144. PMLR, (2020). http:\/\/proceedings.mlr.press\/v119\/ahn20a.html"},{"key":"1356_CR5","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pages 3\u201313, (1982)"},{"issue":"1\u20133","key":"1356_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discret. Appl. Math. 135(1\u20133), 3\u201316 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(02)00290-1","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"1356_CR7","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1515\/dma.2007.030","volume":"17","author":"VE Alekseev","year":"2007","unstructured":"Alekseev, V.E.: An upper bound for the number of maximal independent sets in a graph. Discrete Math. Appl. 17(4), 355\u2013359 (2007). https:\/\/doi.org\/10.1515\/dma.2007.030","journal-title":"Discrete Math. Appl."},{"issue":"1","key":"1356_CR8","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1), 123\u2013134 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(98)00158-3","journal-title":"Theoret. Comput. Sci."},{"key":"1356_CR9","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.neunet.2022.08.008","volume":"155","author":"IR Alkhouri","year":"2022","unstructured":"Alkhouri, I.R., Atia, G.K., Velasquez, A.: A differentiable approach to the maximum independent set problem using dataless neural networks. Neural Netw. 155, 168\u2013176 (2022)","journal-title":"Neural Netw."},{"issue":"4","key":"1356_CR10","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1145\/321607.321608","volume":"17","author":"JG Augustson","year":"1970","unstructured":"Augustson, J.G., Minker, J.: An analysis of some graph theoretical cluster techniques. J. ACM (JACM) 17(4), 571\u2013588 (1970)","journal-title":"J. ACM (JACM)"},{"key":"1356_CR11","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Bonnet, E., D\u00e9pr\u00e9s, H., Esperet, L., Geniet, C., Hilaire, C., Thomass\u00e9, S., Wesolek, A.: Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3006\u20133028. SIAM, (2023)","DOI":"10.1137\/1.9781611977554.ch116"},{"key":"1356_CR12","doi-asserted-by":"publisher","unstructured":"Bonnet, E., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in H-free graphs. In Christophe Paul and Micha\u0142 Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, volume 115 of LIPIcs, pages 17:1\u201317:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.17","DOI":"10.4230\/LIPIcs.IPEC.2018.17"},{"key":"1356_CR13","doi-asserted-by":"publisher","unstructured":"\u00c9douard Bonnet, Nicolas Bousquet, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. When maximum stable set can be solved in FPT time. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 49:1\u201349:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.49","DOI":"10.4230\/LIPIcs.ISAAC.2019.49"},{"issue":"1","key":"1356_CR14","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001). https:\/\/doi.org\/10.1137\/S0097539799359683","journal-title":"SIAM J. Comput."},{"key":"1356_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.dam.2017.11.029","volume":"237","author":"A Brandst\u00e4dt","year":"2018","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent set for $$ {l}$$claw-free graphs in polynomial time. Discret. Appl. Math. 237, 57\u201364 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.11.029","journal-title":"Discret. Appl. Math."},{"key":"1356_CR16","unstructured":"Butenko, S.: Maximum independent set and related problems, with applications. University of Florida, (2003)"},{"key":"1356_CR17","doi-asserted-by":"publisher","unstructured":"Butenko, S., Pardalos, P.M., Sergienko, I., Shylo, V., Stetsyuk, P.: Finding maximum independent sets in graphs arising from coding theory. In Gary\u00a0B. Lamont, Hisham Haddad, George\u00a0A. Papadopoulos, and Brajendra Panda, editors, Proceedings of the 2002 ACM Symposium on Applied Computing (SAC), March 10-14, 2002, Madrid, Spain, pages 542\u2013546. ACM, (2002). https:\/\/doi.org\/10.1145\/508791.508897","DOI":"10.1145\/508791.508897"},{"key":"1356_CR18","doi-asserted-by":"publisher","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 612\u2013623. IEEE, (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00064","DOI":"10.1109\/FOCS54457.2022.00064"},{"issue":"2","key":"1356_CR19","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1137\/19M1249473","volume":"34","author":"M Chudnovsky","year":"2020","unstructured":"Chudnovsky, M., Pilipczuk, M., Pilipczuk, M., Thomass\u00e9, S.: On the maximum weight independent set problem in graphs without induced cycles of length at least five. SIAM J. Discret. Math. 34(2), 1472\u20131483 (2020). https:\/\/doi.org\/10.1137\/19M1249473","journal-title":"SIAM J. Discret. Math."},{"key":"1356_CR20","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Pilipczuk, M., Pilipczuk, M., Thomass\u00e9, S.: Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2260\u20132278, (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.139","DOI":"10.1137\/1.9781611975994.139"},{"issue":"1","key":"1356_CR21","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). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inf. Comput."},{"key":"1356_CR22","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jda.2011.12.012","volume":"14","author":"KK Dabrowski","year":"2012","unstructured":"Dabrowski, K.K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207\u2013213 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.12.012","journal-title":"J. Discrete Algorithms"},{"key":"1356_CR23","doi-asserted-by":"publisher","unstructured":"Dallard, C., Milani\u010d, M., \u0160torgel, K.: Treewidth versus clique number. III. tree-independence number of graphs with a forbidden structure. CoRR, abs\/2206.15092, 2022. arXiv:2206.15092, https:\/\/doi.org\/10.48550\/arXiv.2206.15092","DOI":"10.48550\/arXiv.2206.15092"},{"key":"1356_CR24","doi-asserted-by":"publisher","unstructured":"Dallard, C., Milani\u010d, M., \u0160torgel, K.: Treewidth versus clique number. II. tree-independence number, (2021). https:\/\/arxiv.org\/abs\/2111.04543, https:\/\/doi.org\/10.48550\/ARXIV.2111.04543","DOI":"10.48550\/ARXIV.2111.04543"},{"issue":"1&2","key":"1356_CR25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109\u2013131 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00097-3","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1356_CR26","doi-asserted-by":"publisher","first-page":"1416","DOI":"10.2514\/1.A34931","volume":"58","author":"D Eddy","year":"2021","unstructured":"Eddy, D., Kochenderfer, M.J.: A maximum independent set method for scheduling earth-observing satellite constellations. J. Spacecr. Rocket. 58(5), 1416\u20131429 (2021)","journal-title":"J. Spacecr. Rocket."},{"issue":"4","key":"1356_CR27","doi-asserted-by":"publisher","first-page":"340","DOI":"10.2307\/2785498","volume":"9","author":"E Forsyth","year":"1946","unstructured":"Forsyth, E., Katz, L.: A matrix approach to the analysis of sociometric data: preliminary report. Sociometry 9(4), 340\u2013347 (1946)","journal-title":"Sociometry"},{"issue":"2","key":"1356_CR28","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1021\/ci990262o","volume":"40","author":"EJ Gardiner","year":"2000","unstructured":"Gardiner, E.J., Willett, P., Artymiuk, P.J.: Graph-theoretic techniques for macromolecular docking. J. Chem. Inf. Comput. Sci. 40(2), 273\u2013279 (2000). https:\/\/doi.org\/10.1021\/ci990262o","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"1356_CR29","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"3","key":"1356_CR30","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). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"key":"1356_CR31","doi-asserted-by":"publisher","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on P$$ _{k}$$-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613\u2013624. IEEE, (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"1356_CR32","doi-asserted-by":"publisher","unstructured":"Gartland, P., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Finding large induced sparse subgraphs in C$$ _{\\text{>t}}$$ -free graphs in quasipolynomial time. In Samir Khuller and Virginia\u00a0Vassilevska Williams, editors, STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 330\u2013341. ACM, (2021). https:\/\/doi.org\/10.1145\/3406325.3451034","DOI":"10.1145\/3406325.3451034"},{"issue":"1","key":"1356_CR33","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. Combinat. Theory, Series B 16(1), 47\u201356 (1974)","journal-title":"J. Combinat. Theory, Series B"},{"issue":"1","key":"1356_CR34","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on P$$ _{\\text{6 }}$$-free graphs. ACM Trans. Algorithms 18(1), 4\u201357 (2022). https:\/\/doi.org\/10.1145\/3414473","journal-title":"ACM Trans. Algorithms"},{"key":"1356_CR35","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n$$ ^{\\text{1- }\\varepsilon }$$. In Acta Mathematica, pages 627\u2013636, (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"2","key":"1356_CR36","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). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1356_CR37","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":"1356_CR38","first-page":"116","volume":"38","author":"D K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Gr\u00e1fok \u00e9s m\u00e1trixok. Matematikai \u00e9s Fizikai Lapok 38, 116\u2013119 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"1356_CR39","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.jctb.2023.01.002","volume":"160","author":"T Korhonen","year":"2023","unstructured":"Korhonen, T.: Grid induced minor theorem for graphs of small degree. J. Comb. Theory. Ser. B 160, 206\u2013214 (2023). https:\/\/doi.org\/10.1016\/j.jctb.2023.01.002","journal-title":"J. Comb. Theory. Ser. B"},{"issue":"4","key":"1356_CR40","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10732-017-9337-x","volume":"23","author":"S Lamm","year":"2017","unstructured":"Lamm, S., Sanders, P., Schulz, C., Strash, D., Werneck, R.F.: Finding near-optimal independent sets at scale. J. Heuristics 23(4), 207\u2013229 (2017). https:\/\/doi.org\/10.1007\/s10732-017-9337-x","journal-title":"J. Heuristics"},{"issue":"4","key":"1356_CR41","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6(4), 595\u2013604 (2008). https:\/\/doi.org\/10.1016\/j.jda.2008.04.001","journal-title":"J. Discrete Algorithms"},{"key":"1356_CR42","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in P$$ _{t}$$-free graphs via shrinking the space of induced paths. In Hung\u00a0Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204\u2013209. SIAM, (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.23","DOI":"10.1137\/1.9781611976496.23"},{"issue":"2","key":"1356_CR43","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(2), 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"1356_CR44","doi-asserted-by":"publisher","unstructured":"Pontoizeau, T., Sikora, F., Yger, F., Cazenave, T.: Neural maximum independent set. In Machine Learning and Principles and Practice of Knowledge Discovery in Databases - International Workshops of ECML PKDD 2021, Virtual Event, September 13-17, 2021, Proceedings, Part I, volume 1524 of Communications in Computer and Information Science, pages 223\u2013237. Springer, (2021). https:\/\/doi.org\/10.1007\/978-3-030-93736-2_18","DOI":"10.1007\/978-3-030-93736-2_18"},{"key":"1356_CR45","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92\u2013114, (1986) https:\/\/doi.org\/10.1016\/0095-8956(86)90030-4","DOI":"10.1016\/0095-8956(86)90030-4"},{"issue":"2","key":"1356_CR46","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1356_CR47","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). https:\/\/doi.org\/10.1137\/0206036","journal-title":"SIAM J. Comput."},{"key":"1356_CR48","doi-asserted-by":"publisher","unstructured":"Verweij, B., Aardal, K.: An optimisation algorithm for maximum independent set with applications in map labelling. In Jaroslav Nesetril, editor, Algorithms - ESA \u201999, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings, volume 1643 of Lecture Notes in Computer Science, pages 426\u2013437. Springer, (1999). https:\/\/doi.org\/10.1007\/3-540-48481-7_37","DOI":"10.1007\/3-540-48481-7_37"},{"key":"1356_CR49","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Inf. Comput."},{"issue":"1","key":"1356_CR50","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory of Computing"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01356-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01356-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01356-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:11:26Z","timestamp":1770009086000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01356-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,23]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1356"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01356-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,23]]},"assertion":[{"value":"22 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 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 have no Conflict of interest as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"16"}}