Negative Results on the Stability Problem Within Co-Hereditary Classes

Abstract

Let $S$ be a stable set in a graph $G$, possibly $S=\mathrm{\varnothing }$. The subgraph $G–N[S]$, where $N[S]$ is the closed neighborhood of $S$, is called a \emph{co-stable subgraph} of $G$. We denote by $\text{CSub}(G)$ the set of all co-stable subgraphs of $G$. A class of graphs $\mathcal{P}$ is called \emph{co-hereditary} if $G\in \mathcal{P}$ implies $\text{CSub}(G)\subseteq \mathcal{P}$. Our result: If the set of all minimal forbidden co-stable subgraphs for a non-empty co-hereditary class $\mathcal{P}$ is finite, then Stable Set is an NP-complete problem within $\mathcal{P}$. Also, we prove that the decision problem of recognizing whether a graph has a fixed graph $H$ as a co-stable subgraph is NP-complete for each non-trivial graph $H$.