{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:35:51Z","timestamp":1787319351801,"version":"build-2736575974"},"reference-count":8,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"publisher","award":["2022\/47\/D\/ST6\/03421"],"award-info":[{"award-number":["2022\/47\/D\/ST6\/03421"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Independent Research Fund Denmark","award":["2098-00012B"],"award-info":[{"award-number":["2098-00012B"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J.\u00a0Comput., 44 (2015), pp.\u00a054\u201387] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).<\/jats:p>","DOI":"10.1137\/23m1550530","type":"journal-article","created":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T04:39:12Z","timestamp":1734323952000},"page":"3140-3149","source":"Crossref","is-referenced-by-count":2,"title":["Taming Graphs with No Large Creatures and Skinny Ladders"],"prefix":"10.1137","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4761-3432","authenticated-orcid":true,"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[{"name":"University of Warsaw, 00-927 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":true,"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[{"name":"NHH Norwegian School of Economics, 5045 Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paloma T.","family":"de Lima","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, 2300 Copenhagen, Denmark."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jana","family":"Masa\u0159\u00edkov\u00e1","sequence":"additional","affiliation":[{"name":"University of Warsaw, 00-927 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":true,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, 00-927 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":"University of Warsaw, 00-927 Warsaw, Poland."},{"name":"Warsaw University of Technology, 00-661 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5320-9209","authenticated-orcid":true,"given":"U\u00e9verton S.","family":"Souza","sequence":"additional","affiliation":[{"name":"University of Warsaw, 00-927 Warsaw, Poland."},{"name":"Universidade Federal Fluminense, 24020-141 Rio de Janeiro, Brazil, and Instituto de Matem\u00e1tica Pura e Aplicada, 22460-320, Rio de Janeiro, Brazil."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,12,16]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.003"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"ref4","unstructured":"J. Gajarsk\u00fd, L. Jaffke, P. T. Lima, J. Novotn\u00e1, M. Pilipczuk, P. Rz\u0104\u017cewski, and U. S. Souza, Taming Graphs with No Large Creatures and Skinny Ladders, in Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), Leibniz International Proceedings in Informatics (LIPIcs) 244, 2022, 58, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/16996."},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"P. Gartland and D. Lokshtanov, Graph classes with few minimal separators. I. Finite forbidden induced subgraphs, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023, pp. 3063\u20133097, https:\/\/doi.org\/10.1137\/1.9781611977554.ch119.","DOI":"10.1137\/1.9781611977554.ch119"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"P. Gartland and D. Lokshtanov, Graph classes with few minimal separators. II. A dichotomy, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023, pp. 3098\u20133178, https:\/\/doi.org\/10.1137\/1.9781611977554.ch120.","DOI":"10.1137\/1.9781611977554.ch120"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30786-8_29"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.37236\/9428"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1550530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:47:58Z","timestamp":1787316478000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1550530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,16]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/23M1550530"],"URL":"https:\/\/doi.org\/10.1137\/23m1550530","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,16]]}}}