{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T09:10:01Z","timestamp":1789722601493,"version":"4.0.1"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1763817"],"award-info":[{"award-number":["DMS-1763817"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of [Formula: see text] for any [Formula: see text]. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In [Formula: see text]-free graphs, that is, graphs not containing a fixed graph [Formula: see text] as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever [Formula: see text] contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of [Formula: see text] is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs [Formula: see text] such as [Formula: see text], [Formula: see text], the claw, or the fork. We prove that for every such \u201cpossibly tractable\u201d graph [Formula: see text] there exists an algorithm that, given an [Formula: see text]-free graph [Formula: see text] and an accuracy parameter [Formula: see text], finds an independent set in [Formula: see text] of cardinality within a factor of [Formula: see text] of the optimum in time exponential in a polynomial of [Formula: see text] and [Formula: see text]. Furthermore, an independent set of maximum size can be found in subexponential time [Formula: see text]. That is, we show that for every graph [Formula: see text] for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in [Formula: see text]-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.<\/jats:p>","DOI":"10.1137\/20m1333778","type":"journal-article","created":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T04:01:18Z","timestamp":1708488078000},"page":"47-86","source":"Crossref","is-referenced-by-count":3,"title":["Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \\(\\boldsymbol{H}\\)-Free Graphs"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":true,"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[{"name":"Mathematics Department, Princeton University, Princeton, NJ 08544 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":true,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"Institut Universitaire de France, Laboratoire d\u2019Informatique du Parall\u00e9lisme, UMR 5668 ENS Lyon, CNRS, UCBL, INRIA, Universit\u00e9 de Lyon, Lyon, 69364, France."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,2,21]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"T. Abrishami, M. Chudnovsky, C. Dibek, and P. Rzazewski, Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, J. S. Naor and N. Buchbinder eds. SIAM, Philadelphia, 2022, pp. 1448\u20131470, https:\/\/doi.org\/10.1137\/1.9781611977073.61.","DOI":"10.1137\/1.9781611977073.61"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzazewski, and P. D. Seymour, Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, D. Marx ed. SIAM, Philadelphia, 2021, pp. 1948\u20131964, https:\/\/doi.org\/10.1137\/1.9781611976465.116.","DOI":"10.1137\/1.9781611976465.116"},{"key":"ref3","unstructured":"T. Abrishami, M. Chudnovsky, M. Pilipczuk, and P. Rz\u0105\u017cewski, Max Weight Independent Set in Sparse Graphs with No Long Claws, preprint, https:\/\/arxiv.org\/abs\/2309.16995, 2023."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0479-5"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.10.003"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.06.016"},{"key":"ref8","unstructured":"M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, and P. Rzazewski, Sparse Induced Subgraphs in \\({P}_6\\)-free Graphs, preprint, https:\/\/arxiv.org\/abs\/2307.07330."},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomass\u00e9, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \\(H\\)-free Graphs, preprint, http:\/\/arxiv.org\/abs\/1907.04585, 2019.","DOI":"10.1137\/1.9781611975994.139"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249473"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomass\u00e9, 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, S. Chawla, ed. SIAM, Philadelphia, 2020, pp. 2260\u20132278, https:\/\/doi.org\/10.1137\/1.9781611975994.139.","DOI":"10.1137\/1.9781611975994.139"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky and P. D. Seymour, The structure of claw-free graphs, in Surveys in Combinatorics, Invited Lectures from the Twentieth British Combinatorial Conference, Durham, UK, 2005, London Math. Soc. Lecture Note Ser. 327, B. S. Webb, ed. Cambridge University Press, Cambridge, 2005, pp. 153\u2013171.","DOI":"10.1017\/CBO9780511734885.008"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2334-4"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"Y. Faenza, G. Oriolo, and G. Stauffer, An algorithmic decomposition of claw-free graphs leading to an \\({O}(n^3)\\)-algorithm for the weighted stable set problem, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, 2011, D. Randall, ed. SIAM, Philadelphia, 2011, pp. 630\u2013646, https:\/\/doi.org\/10.1137\/1.9781611973082.49.","DOI":"10.1137\/1.9781611973082.49"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2629600"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"ref18","volume-title":"Computers and Intractability","volume":"29","author":"Garey M. R.","year":"2002"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"P. Gartland and D. Lokshtanov, Independent set on \\({P}_k\\)-free graphs in quasi-polynomial time, in Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, 2020, S. Irani, ed. IEEE, 2020, pp. 613\u2013624, https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063.","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"P. Gartland, D. Lokshtanov, T. Masar\u00edk, M. Pilipczuk, M. Pilipczuk, and P. Rzazewski, Maximum Weight Independent Set in Graphs with No Long Claws in Quasi-polynomial Time, preprint, https:\/\/arxiv.org\/abs\/2305.15738, 2023.","DOI":"10.1145\/3618260.3649791"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzazewski, Finding large induced sparse subgraphs in \\(C_{\\gt t}\\)-free graphs in quasipolynomial time, in STOC \u201921: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 2021, S. Khuller and V. V. Williams, eds. ACM, 2021, pp. 330\u2013341, https:\/\/doi.org\/10.1145\/3406325.3451034.","DOI":"10.1145\/3406325.3451034"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00395-0"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.04.010"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3414473"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"V. Guruswami and A. K. Sinop, The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, 2011, D. Randall, ed. SIAM, Philadelphia, 2011, pp. 1615\u20131626, https:\/\/doi.org\/10.1137\/1.9781611973082.125.","DOI":"10.1137\/1.9781611973082.125"},{"key":"ref26","doi-asserted-by":"crossref","first-page":"413","DOI":"10.4064\/am-19-3-4-413-441","volume":"19","author":"Gy\u00e1rf\u00e1s A.","year":"1987","journal-title":"Appl. Math."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, M. Vatshelle, and Y. Villanger, Independent set in \\({P}_5\\)-free graphs in polynomial time, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, 2014, C. Chekuri, ed. SIAM, Philadelphia, 2014, pp. 570\u2013581, https:\/\/doi.org\/10.1137\/1.9781611973402.43.","DOI":"10.1137\/1.9781611973402.43"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.004"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.10.004"},{"key":"ref32","unstructured":"K. Majewski, T. Masar\u00edk, J. Novotn\u00e1, K. Okrasa, M. Pilipczuk, P. Rzazewski, and M. Sokolowski, Max weight independent set in graphs with no long claws: An analog of the gy\u00e1rf\u00e1s\u2019 path argument, in Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 2022, Paris, France, M. Bojanczyk, E. Merelli, and D. P. Woodruff, eds. LIPIcs. Leibniz Int. Proc. Inform. 229, Wadern, 2022, 93, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.93."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.03.044"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"D. Nakamura and A. Tamura, The generalized stable set problem for claw-free bidirected graphs, in Proceedings of the, 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, Houston, TX, 1998, Proceedings, Lecture Notes in Comput. Sci. 1412, R. E. Bixby, E. A. Boyd, and R. Z. R\u00edos-Mercado, eds. Springer, 1998, pp. 69\u201383, https:\/\/doi.org\/10.1007\/3-540-69346-7_6.","DOI":"10.1007\/3-540-69346-7_6"},{"key":"ref36","unstructured":"P. Nobili and A. Sassano, An \\({O}(n^2 \\log n)\\) Algorithm for the Weighted Stable Set Problem in Claw-free Graphs, preprint, http:\/\/arxiv.org\/abs\/1501.05775, 2015."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1080-9"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"G. Oriolo, U. Pietropaoli, and G. Stauffer, A new algorithm for the maximum weighted stable set problem in claw-free graphs, in  Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008, Bertinoro, Italy, 2008, Lecture Notes in Comput. Sci. 5035, A. Lodi, A. Panconesi, and G. Rinaldi, eds. Springer, 2008, pp. 77\u201396, https:\/\/doi.org\/10.1007\/978-3-540-68891-4_6.","DOI":"10.1007\/978-3-540-68891-4_6"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk, M. Pilipczuk, and P. Rzazewski, Quasi-polynomial-time algorithm for Independent Set in \\({P}_t\\)-free graphs via shrinking the space of induced paths, in Proceedings of the 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, 2021, H. V. Le and V. King, eds. SIAM, Philadelphia, 2021, pp. 204\u2013209, https:\/\/doi.org\/10.1137\/1.9781611976496.23.","DOI":"10.1137\/1.9781611976496.23"},{"key":"ref40","first-page":"307","volume":"2","author":"Poljak S.","year":"1974","journal-title":"Comment. Math. Univ. Carolin."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1333778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:24Z","timestamp":1787336244000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1333778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1137\/20M1333778"],"URL":"https:\/\/doi.org\/10.1137\/20m1333778","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,21]]}}}