Weighted well-covered graphs and complexity questions

Authors: I. E. Zverovich

ABSTRACT

A weighted graph G is called well-covered if all its maximal stable sets have the same weight. This common weight is the value of G. Let S be a stable set of G (possibly, $S = \emptyset$). The subgraph $G - N[S]$ is called a co-stable subgraph of G. We denote by Sub(G) the set of all co-stable subgraphs of G (considered up to isomorphism). A class of weighted graphs P is called co-hereditary if it is closed under taking co-stable subgraphs, i.e., $G \in \mathcal{P}$ implies ${\rm CSub}(G) \subseteq \mathcal{P}$.

We note that the class $\mathcal{WW}$ of all weighted well-covered graphs is co-hereditary and characterize $\mathcal{WW}$ in terms of forbidden co-stable subgraphs.

Then we use a reduction from Satisfiability to show that the following decision problems are NP-complete.

Decision Problem 1 (Co-Stable Subgraph).
Instance: A graph $G$ and a set $U \subseteq V(G)$ that induces a subgraph $H$.
Question: Is $H$ a co-stable subgraph of $G$?

Decision Problem 2 (Co-Stable Subgraph $H$).
Instance: A graph $G$.
Question: Is $H$ a co-stable subgraph of $G$?

Let $\Delta(G)$ be the maximum vertex degree of a graph $G$. We show that recognizing weighted well-covered graphs with bounded $\Delta(G)$ can be done in polynomial time.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-06.ps.gz