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$?
