Graphs with polynomially many minimal separators

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

Abstract

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

Original languageEnglish (US)
Pages (from-to)248-280
Number of pages33
JournalJournal of Combinatorial Theory. Series B
Volume152
DOIs
StatePublished - Jan 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Induced subgraph
  • Minimal separator
  • Prism
  • Pyramid
  • Theta
  • Turtle

Fingerprint

Dive into the research topics of 'Graphs with polynomially many minimal separators'. Together they form a unique fingerprint.

Cite this