Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is an induced subgraph of a well-covered graph: for instance, find a clique cover of $G$, and add one more vertex to each of the cliques in the cover. Smaller clique covers lead to well-covered supergraphs of $G$ with fewer vertices. Which leads to the following problem:

Input: a graph $G$ and a number $k$

Output: yes if $G$ is an induced subgraph of a $k$-vertex well-covered graph, no otherwise

What is known if anything about the complexity of this problem? Testing whether a graph is well-covered is coNP-complete, so the obvious complexity class for finding a small well-covered completion is $\Sigma^P_2$ — but is it complete for $\Sigma^P_2$?

share|cite|improve this question
is this similar to kalai's idea, "It will be interesting to understand graphs where this property [well covered] holds for all induced subgraphs"? – vzn Feb 20 '13 at 20:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.