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

  • 1
    $\begingroup$ is this similar to kalai's idea, "It will be interesting to understand graphs where this property [well covered] holds for all induced subgraphs"? $\endgroup$
    – vzn
    Commented Feb 20, 2013 at 20:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.