{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:53Z","timestamp":1787340653283,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","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\/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"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["A9550-19-1-0187"],"award-info":[{"award-number":["A9550-19-1-0187"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1800053"],"award-info":[{"award-number":["DMS-1800053"]}],"id":[{"id":"10.13039\/100000001","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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By [Formula: see text], we denote a path on [Formula: see text] vertices. In this paper, we give polynomial-time algorithms for the following problems: the maximum weight independent set problem in long-hole\u2013free graphs and the feedback vertex set problem in [Formula: see text]-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended [Formula: see text] is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let [Formula: see text] be the class of graphs excluding an extended [Formula: see text] and holes of length at least 6 as induced subgraphs; [Formula: see text] contains all long-hole\u2013free graphs and all [Formula: see text]-free graphs. We show that, given an [Formula: see text]-vertex graph [Formula: see text] with vertex weights and an integer [Formula: see text], one can, in time, [Formula: see text] find a maximum-weight induced subgraph of [Formula: see text] of treewidth less than [Formula: see text]. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitt\u00e9 and Todinca [ SIAM J.\u00a0Comput., 31 (2001), pp.\u00a0212\u2013232] and extended by Fomin, Todinca, and Villanger [ SIAM J.\u00a0Comput., 44 (2015), pp.\u00a054\u201387], this framework allows us to solve a wide variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than [Formula: see text] for fixed [Formula: see text], in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the maximum weight independent set problem within this framework (e.g., for [Formula: see text]-free [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp.\u00a0570\u2013581] or [Formula: see text]-free graphs [Grzesik, Klimo\u0161ov\u00e1, Pilipczuk, and Pilipczuk, ACM Trans.\u00a0Algorithms, 18 (2022), pp.\u00a04:1\u20134:57]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here, we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each PMC: a superset of the maximal clique that intersects the sought solution only in the vertices of the PMC. This strengthening of the framework not only allows us to obtain our main result but also leads to significant simplifications of the reasoning in previous papers.<\/jats:p>","DOI":"10.1137\/20m1383732","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T04:02:03Z","timestamp":1717128123000},"page":"624-647","source":"Crossref","is-referenced-by-count":2,"title":["Induced Subgraphs of Bounded Treewidth and the Container Method"],"prefix":"10.1137","volume":"53","author":[{"given":"Tara","family":"Abrishami","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ 08544 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":true,"given":"Maria","family":"Chudnovsky","sequence":"additional","affiliation":[{"name":"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, Banacha 2, 02-097 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":true,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Information Science, Warsaw University of Technology, Koszykowa 75, 00-662 Warsaw, Poland and Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ 08544 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,5,31]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.116"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"ref3","unstructured":"J. Balogh, R. Morris, and W. Samotij, The method of hypergraph containers, in Proceedings of the International Congress of Mathematics, Rio de Janeiro, 2018, pp. 3045\u20133078."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.06.015"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.11.018"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0474-x"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.09.015"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.10.031"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028791"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/090750822"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1461-x"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.09.033"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, and P. Rz\u0105\u017cewski, Sparse induced subgraphs in \\(P_6\\)-free graphs, in Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, D. P. Woodruff, ed. SIAM, Philadelphia, 2024, pp. 5291\u20135299, https:\/\/doi.org\/10.1137\/1.9781611977912.190.","DOI":"10.1137\/1.9781611977912.190"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249473"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"ref19","unstructured":"M. Chudnovsky, S. Thomass\u00e9, N. Trotignon, and K. Vuskovic, Maximum Independent Sets in (Pyramid, even Hole)-Free Graphs, preprint, arXiv:1912.11246 [cs.DM], 2019."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00706-6"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"ref24","unstructured":"F. V. Fomin and Y. Villanger, Finding induced subgraphs via minimal triangulations, in 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, LIPIcs 5, J. Marion and T. Schwentick, eds. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2010, pp. 383\u2013394, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2470."},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"P. Gartland and D. Lokshtanov, Independent set on \\({P}_k\\)-free graphs in quasi-polynomial time, in 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, S. Irani, ed. IEEE, 2020, pp. 613\u2013624, https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063.","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rz\u0105\u017cewski, Finding large induced sparse subgraphs in \\(C_{\\gt t}\\)-free graphs in quasipolynomial time, in STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, S. Khuller and V. V. Williams, eds. ACM, New York, 2021, pp. 330\u2013341, https:\/\/doi.org\/10.1145\/3406325.3451034.","DOI":"10.1145\/3406325.3451034"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.37236\/9473"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1145\/3414473"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems, in Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, R. E. Miller and J. W. Thatcher, eds. Plenum Press, New York, 1972, pp. 85\u2013103, https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4684-2001-2_9, https:\/\/doi.org\/10.1007\/978-1-4684-2001-2.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref31","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, Oregon, USA, January 5-7, 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":"ref32","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk, M. Pilipczuk, and P. Rz\u0105\u017cewski, Quasi-polynomial-time algorithm for Independent Set in \\({P}_t\\)-free graphs via shrinking the space of induced paths, in 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 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":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1383732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:45Z","timestamp":1787337765000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1383732"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,31]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1137\/20M1383732"],"URL":"https:\/\/doi.org\/10.1137\/20m1383732","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,31]]}}}