Taming Graphs with No Large Creatures and Skinny Ladders

Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht

Titel: Taming Graphs with No Large Creatures and Skinny Ladders

Beteiligte: Gajarský, Jakub [Verfasser:in]; Jaffke, Lars [Verfasser:in]; Lima, Paloma T. [Verfasser:in]; Novotná, Jana [Verfasser:in]; Pilipczuk, Marcin [Verfasser:in]; Rzążewski, Paweł [Verfasser:in]; Souza, Uéverton S. [Verfasser:in]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ESA.2022.58

Schlagwörter: Minimal separator ; hereditary graph class

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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).

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: