LIPIcs.ESA.2022.58.pdf
- Filesize: 1.25 MB
- 8 pages
Document
Taming Graphs with No Large Creatures and Skinny Ladders
Authors
Jakub Gajarský 
,
Lars Jaffke ,
Paloma T. Lima ,
Jana Novotná ,
Marcin Pilipczuk ,
Paweł Rzążewski ,
Uéverton S. Souza
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
Cite As Get BibTex
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.58
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).
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph theory
Keywords
- Minimal separator
- hereditary graph class
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, and Kristina Vuškovič. Graphs with polynomially many minimal separators. J. Comb. Theory, Ser. B, 152:248-280, 2022. URL: https://doi.org/10.1016/j.jctb.2021.10.003.
- Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput., 31(1):212-232, 2001. URL: https://doi.org/10.1137/S0097539799359683.
- Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
- Peter Gartland and Daniel Lokshtanov. Dominated minimal separators are tame (nearly all others are feral). CoRR, abs/2007.08761, 2020. URL: http://arxiv.org/abs/2007.08761.
- Martin Milanič and Nevena Pivač. Minimal separators in graph classes defined by small forbidden induced subgraphs. In Ignasi Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, volume 11789 of Lecture Notes in Computer Science, pages 379-391. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30786-8_29.
- Martin Milanič and Nevena Pivač. Polynomially bounding the number of minimal separators in graphs: Reductions, sufficient conditions, and a dichotomy theorem. Electron. J. Comb., 28(1):P1.41, 2021. URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p41, URL: https://doi.org/10.37236/9428.