Graphs with polynomially many minimal separators

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

doi:10.1016/j.jctb.2021.10.003

Graphs with polynomially many minimal separators

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

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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 language	English (US)
Pages (from-to)	248-280
Number of pages	33
Journal	Journal of Combinatorial Theory. Series B
Volume	152
DOIs	https://doi.org/10.1016/j.jctb.2021.10.003
State	Published - 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

Access to Document

10.1016/j.jctb.2021.10.003

Cite this

@article{da26e7796f224c32857d3780a9bfbc5a,

title = "Graphs with polynomially many minimal separators",

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.",

keywords = "Induced subgraph, Minimal separator, Prism, Pyramid, Theta, Turtle",

author = "Tara Abrishami and Maria Chudnovsky and Cemil Dibek and St{\'e}phan Thomass{\'e} and Nicolas Trotignon and Kristina Vu{\v s}kovi{\'c}",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier Inc.",

year = "2022",

month = jan,

doi = "10.1016/j.jctb.2021.10.003",

language = "English (US)",

volume = "152",

pages = "248--280",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Graphs with polynomially many minimal separators

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Dibek, Cemil

AU - Thomassé, Stéphan

AU - Trotignon, Nicolas

AU - Vušković, Kristina

PY - 2022/1

Y1 - 2022/1

N2 - 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.

AB - 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.

KW - Induced subgraph

KW - Minimal separator

KW - Prism

KW - Pyramid

KW - Theta

KW - Turtle

UR - http://www.scopus.com/inward/record.url?scp=85117580499&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85117580499&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2021.10.003

DO - 10.1016/j.jctb.2021.10.003

M3 - Article

AN - SCOPUS:85117580499

SN - 0095-8956

VL - 152

SP - 248

EP - 280

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Graphs with polynomially many minimal separators

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this