{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T21:55:31Z","timestamp":1770069331382,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"BSF","award":["2018302"],"award-info":[{"award-number":["2018302"]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2008838"],"award-info":[{"award-number":["CCF-2008838"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Polish National Science Centre","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["714704 and 677651"],"award-info":[{"award-number":["714704 and 677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451034","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"330-341","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Finding large induced sparse subgraphs in\n            <i>\n              c\n              <sub>&gt;t<\/sub>\n            <\/i>\n            -free graphs in quasipolynomial time"],"prefix":"10.1145","author":[{"given":"Peter","family":"Gartland","sequence":"first","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of 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, Poland \/ University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.116"},{"key":"e_1_3_2_1_2_1","volume-title":"The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics","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. Combinatorial-algebraic methods in applied mathematics, 1982. Pages 3\u201313."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00290-1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_13"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0479-5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0649-5"},{"key":"e_1_3_2_1_7_1","volume-title":"Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. CoRR, abs\/1907.04585","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. arxiv:1907.04585"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.139"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_10_1","volume-title":"Graph Structure and Monadic Second-Order Logic \u2013- A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications. 138","author":"Courcelle Bruno","unstructured":"Bruno Courcelle and Joost Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic \u2013- A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications. 138, Cambridge University Press. isbn:978-0-521-89833-1 http:\/\/www.cambridge.org\/fr\/knowledge\/isbn\/item5758776\/?site_locale=fr_FR"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160509"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2018"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"e_1_3_2_1_14_1","volume-title":"Finding large induced sparse subgraphs in C_>t-free graphs in quasipolynomial time. CoRR, abs\/2007.11402","author":"Gartland Peter","year":"2021","unstructured":"Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Pawe\u0142 Rz\\k a\\.zewski. 2021. Finding large induced sparse subgraphs in C_>t-free graphs in quasipolynomial time. CoRR, abs\/2007.11402, 2021. arxiv:2007.11402"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.77"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"e_1_3_2_1_18_1","volume-title":"Constant Congestion Brambles. CoRR, abs\/2008.02133","author":"Hatzel Meike","year":"2020","unstructured":"Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, and Manuel Sorge. 2020. Constant Congestion Brambles. CoRR, abs\/2008.02133, 2020. arxiv:2008.02133"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.43"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00745-z"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.23"},{"key":"e_1_3_2_1_25_1","unstructured":"Marcin Pilipczuk Micha\u0142 Pilipczuk and Sebastian Siebertz. Winter semester 2019\/20. Lecture notes for the course Sparsity. https:\/\/www.mimuw.edu.pl\/ mp248287\/sparsity2\/"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451034","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451034","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":26,"alternative-id":["10.1145\/3406325.3451034","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451034","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}