Maximum independent sets in (pyramid, even hole)-free graphs

Maria Chudnovsky (1) , Stéphan Thomassé (2, 3, 4) , Nicolas Trotignon (3, 4) , Kristina Vušković (5)

1 Columbia University [New York]
2 LAPCS - Laboratoire de Probabilités, Combinatoire et Statistique
3 MC2 - Modèles de calcul, Complexité, Combinatoire
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 School of Computing [Leeds]

A \emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is \emph{even-hole-free} if it does not contain a hole on an even number of vertices. A \emph{pyramid} is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident with $a$. We give a polynomial time algorithm to compute a maximum weighted independent set in a even-hole-free graph that contains no pyramid as an induced subgraph. Our result is based on a decomposition theorem and on bounding the number of minimal separators. All our results hold for a slightly larger class of graphs, the class of (square, prism, pyramid, theta, even wheel)-free graphs.

Domaines: Mathématique discrète [cs.DM]

Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković. Maximum independent sets in (pyramid, even hole)-free graphs. 2021. ⟨hal-02424059⟩