{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:18Z","timestamp":1750219698631,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["714704 and 948057"],"award-info":[{"award-number":["714704 and 948057"]}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            We revisit recent developments for the\n            <jats:sc>Maximum Weight Independent Set<\/jats:sc>\n            problem in graphs excluding a subdivided claw\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t,t,t<\/jats:italic>\n            <\/jats:sub>\n            as an induced subgraph and provide a subexponential-time algorithm with improved running time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{\\mathcal {O}(\\sqrt {nt}\\log n)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and a quasipolynomial-time approximation scheme with improved running time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{\\mathcal {O}(\\varepsilon ^{-1}t \\log ^{5} n)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>\n          <jats:p>\n            The Gy\u00e1rf\u00e1s\u2019 path argument, a powerful tool that is the main building block for many algorithms in\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sub>\n            -free graphs, ensures that given an\n            <jats:italic>n<\/jats:italic>\n            -vertex\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sub>\n            -free graph, in polynomial time we can find a set\n            <jats:italic>P<\/jats:italic>\n            of at most\n            <jats:italic>t<\/jats:italic>\n            -1 vertices such that every connected component of\n            <jats:italic>G-N[P]<\/jats:italic>\n            has at most\n            <jats:italic>n<\/jats:italic>\n            \/2 vertices. Our main technical contribution is an analog of this result for\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t,t,t<\/jats:italic>\n            <\/jats:sub>\n            -free graphs: given an\n            <jats:italic>n<\/jats:italic>\n            -vertex\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t,t,t<\/jats:italic>\n            <\/jats:sub>\n            -free graph, in polynomial time we can find a set\n            <jats:italic>P<\/jats:italic>\n            of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {O}(t \\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of\n            <jats:italic>G-N[P]<\/jats:italic>\n            such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most\n            <jats:italic>n<\/jats:italic>\n            \/2 vertices.\n          <\/jats:p>","DOI":"10.1145\/3636422","type":"journal-article","created":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T12:17:29Z","timestamp":1706098649000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gy\u00e1rf\u00e1s\u2019 Path Argument"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3922-7953","authenticated-orcid":false,"given":"Konrad","family":"Majewski","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7955-4692","authenticated-orcid":false,"given":"Jana","family":"Masa\u0159\u00edkov\u00e1","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1414-3507","authenticated-orcid":false,"given":"Karolina","family":"Okrasa","sequence":"additional","affiliation":[{"name":"Warsaw University of Technology, Warsaw, Poland and University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Warsaw University of Technology, Warsaw, Poland and University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8309-0141","authenticated-orcid":false,"given":"Marek","family":"Soko\u0142owski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,14]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws","volume":"2107","author":"Abrishami Tara","year":"2021","unstructured":"Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Pawe\u0142 Rz\u0105\u017cewski. 2021. Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws. CoRR abs\/2107.05434 (2021).","journal-title":"CoRR"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","unstructured":"Tara Abrishami Maria Chudnovsky Cemil Dibek and Pawe\u0142 Rz\u0105\u017cewski. 2022. 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 \u201922). 1448\u20131470. 10.1137\/1.9781611977073.61","DOI":"10.1137\/1.9781611977073.61"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.003"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","unstructured":"Tara Abrishami Maria Chudnovsky Marcin Pilipczuk Pawe\u0142 Rz\u0105\u017cewski and Paul D. Seymour. 2021. Induced subgraphs of bounded treewidth and the container method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921). 1948\u20131964. 10.1137\/1.9781611976465.116","DOI":"10.1137\/1.9781611976465.116"},{"key":"e_1_3_2_6_2","unstructured":"Tara Abrishami Maria Chudnovsky Marcin Pilipczuk and Pawe\u0142 Rz\u0105\u017cewski. 2023. Max weight independent set in sparse graphs with no long claws. arXiv:2309.16995 [cs.DS] (2023)."},{"key":"e_1_3_2_7_2","first-page":"3","article-title":"The effect of local constraints on the complexity of determination of the graph independence number","author":"Alekseev Vladimir E.","year":"1982","unstructured":"Vladimir E. Alekseev. 1982. The effect of local constraints on the complexity of determination of the graph independence number. In Combinatorial-Algebraic Methods in Applied Mathematics. Gorkiy University Press, 3\u201313.","journal-title":"Combinatorial-Algebraic Methods in Applied Mathematics."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00387-1"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0479-5"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_3_2_12_2","article-title":"Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs","volume":"1907","author":"Chudnovsky Maria","year":"2019","unstructured":"Maria Chudnovsky, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and St\u00e9phan Thomass\u00e9. 2019. Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs. CoRR abs\/1907.04585 (2019).","journal-title":"CoRR"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Maria Chudnovsky Marcin Pilipczuk Micha\u0142 Pilipczuk and St\u00e9phan Thomass\u00e9. 2020. 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 \u201920). 2260\u20132278. 10.1137\/1.9781611975994.139","DOI":"10.1137\/1.9781611975994.139"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","unstructured":"Maria Chudnovsky and Paul D. Seymour. 2005. The structure of claw-free graphs. In Surveys in Combinatorics 2005 Bridget S. Webb (Ed.). London Mathematical Society Lecture Notes Series Vol. 327. Cambridge University Press 153\u2013171. 10.1017\/cbo9780511734885.008","DOI":"10.1017\/cbo9780511734885.008"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2334-4"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"e_1_3_2_18_2","article-title":"Maximum weight independent set in graphs with no long claws in quasi-polynomial time","volume":"2305","author":"Gartland Peter","year":"2023","unstructured":"Peter Gartland, Daniel Lokshtanov, Tom\u00e1\u0161 Masa\u0159\u00edk, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Pawe\u0142 Rz\u0105\u017cewski. 2023. Maximum weight independent set in graphs with no long claws in quasi-polynomial time. CoRR abs\/2305.15738 (2023).","journal-title":"CoRR"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451034"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Andrzej Grzesik Tereza Klimo\u0161ov\u00e1 Marcin Pilipczuk and Micha\u0142 Pilipczuk. 2019. Polynomial-time algorithm for maximum weight independent set on \\(P_6\\) -free graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201919). 1257\u20131271. 10.1137\/1.9781611975482.77","DOI":"10.1137\/1.9781611975482.77"},{"key":"e_1_3_2_21_2","first-page":"801","volume-title":"Infinite and Finite Sets, Vol. II","author":"Gy\u00e1rf\u00e1s Andr\u00e1s","year":"1975","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s. 1975. On Ramsey covering-numbers. In Infinite and Finite Sets, Vol. II. Colloquia Mathematica Societatis Janos Bolyai, No. 10. North-Holland, Amsterdam, 801\u2013816."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s. 1987. Problems from the world surrounding perfect graphs. In Proceedings of the International Conference on Combinatorial Analysis and Its Applications. 413\u2013441. 10.4064\/am-19-3-4-413-441","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","unstructured":"Daniel Lokshtanov Martin Vatshelle and Yngve Villanger. 2014. Independent set in \\({P}_5\\) -free graphs in polynomial time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914). 570\u2013581. 10.1137\/1.9781611973402.43","DOI":"10.1137\/1.9781611973402.43"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.93"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Marcin Pilipczuk Micha\u0142 Pilipczuk and Pawe\u0142 Rz\u0105\u017cewski. 2021. 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 \u201921). 204\u2013209. 10.1137\/1.9781611976496.23","DOI":"10.1137\/1.9781611976496.23"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636422","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3636422","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:41Z","timestamp":1750178141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,14]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3636422"],"URL":"https:\/\/doi.org\/10.1145\/3636422","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,3,14]]},"assertion":[{"value":"2022-11-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}