{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T03:47:03Z","timestamp":1770436023669,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"European Research Council","award":["714704 and 948057"],"award-info":[{"award-number":["714704 and 948057"]}]},{"name":"NSF-EPSRC","award":["DMS-2120644"],"award-info":[{"award-number":["DMS-2120644"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-22-1-008"],"award-info":[{"award-number":["FA9550-22-1-008"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["DMS-2202961"],"award-info":[{"award-number":["DMS-2202961"]}]},{"name":"BARC, supported by the VILLUM Foundation","award":["16582"],"award-info":[{"award-number":["16582"]}]},{"name":"Polish National Science Centre SONATA BIS-12","award":["2022\/46\/E\/ST6\/00143"],"award-info":[{"award-number":["2022\/46\/E\/ST6\/00143"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf{CMSO}_{2}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    logic, most notably\n                    <jats:sc>Feedback Vertex Set<\/jats:sc>\n                    , are polynomial-time solvable in the class of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(P_{6}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -free graphs. This generalizes the work of Grzesik, Klimo\u0161ov\u00e1, Pilipczuk, and Pilipczuk on the\n                    <jats:sc>Maximum Weight Independent Set<\/jats:sc>\n                    problem in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(P_{6}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -free graphs [SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rz\u0105\u017cewski, and Seymour on problems in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(P_{5}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -free graphs [SODA 2021].\n                  <\/jats:p>\n                  <jats:p>\n                    The key step is a new generalization of the framework of\n                    <jats:italic toggle=\"yes\">potential maximal cliques<\/jats:italic>\n                    . We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their\n                    <jats:italic toggle=\"yes\">carvers<\/jats:italic>\n                    : vertex sets that contain the same vertices from the sought solution and have similar separation properties.\n                  <\/jats:p>","DOI":"10.1145\/3785003","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T18:28:14Z","timestamp":1765823294000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Induced Subgraphs in\n                    <b>\n                      <i>P<\/i>\n                    <\/b>\n                    <sub>\n                      <b>6<\/b>\n                    <\/sub>\n                    -free Graphs"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":false,"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9884-3406","authenticated-orcid":false,"given":"Rose","family":"McCarty","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, New Jersey, USA and Institute of Informatics, 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":"Institute of Informatics, University of Warsaw, Warsaw, Poland and IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, 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 Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1383732"},{"key":"e_1_3_2_3_2","first-page":"3","volume-title":"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. In Combinatorial-Algebraic Methods in Applied Mathematics. Gorkiy University Press, 3\u201313."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00387-1"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.005"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0474-x"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_9_2","volume-title":"Encyclopedia of Mathematics and Its Applications","author":"Courcelle Bruno","year":"2012","unstructured":"Bruno Courcelle and Joost Engelfriet. 2012. Graph structure and monadic second-order logic \u2013 A language-theoretic approach. In Encyclopedia of Mathematics and Its Applications, Vol. 138, Cambridge University Press. Retrieved from https:\/\/www.cambridge.org\/core\/books\/graph-structure-and-monadic-secondorder-logic\/64B5637C839631A748DA06DD5BFBE52F"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"e_1_3_2_12_2","first-page":"383","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS \u201910)","volume":"5","author":"Fomin Fedor V.","year":"2010","unstructured":"Fedor V. Fomin and Yngve Villanger. 2010. Finding induced subgraphs via minimal triangulations. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS \u201910). Jean-Yves, Marion, and Thomas, Schwentick (Eds.), Vol. 5, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 383\u2013394."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451034"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.37236\/9473"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3414473"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.130"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/1024196"},{"key":"e_1_3_2_20_2","first-page":"570","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914)","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. Independent set in \\(P_{5}\\) -free graphs in polynomial time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914). SIAM, 570\u2013581."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15914-5_30"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/22M1468864"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.05.019"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.23"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T14:22:47Z","timestamp":1770387767000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3785003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3785003"],"URL":"https:\/\/doi.org\/10.1145\/3785003","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,6]]},"assertion":[{"value":"2024-04-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}