dc.contributor.author | Gajarský, Jakub | |
dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Lima, Paloma Thome de | |
dc.contributor.author | Novotná, Jana | |
dc.contributor.author | Pilipczuk, Marcin | |
dc.contributor.author | Rzążewski, Paweł | |
dc.contributor.author | Souza, Uéverton S. | |
dc.date.accessioned | 2023-01-04T14:01:24Z | |
dc.date.available | 2023-01-04T14:01:24Z | |
dc.date.created | 2023-01-03T09:51:14Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3041004 | |
dc.description.abstract | We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] 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 𝒢. 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). | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Taming Graphs with No Large Creatures and Skinny Ladders | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2022 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.ESA.2022.58 | |
dc.identifier.cristin | 2099371 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 58:1-58:8 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2022, 244, 58:1-58:8. | en_US |
dc.source.volume | 244 | en_US |