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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
1  
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

 
discard

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

Browse other questions tagged or ask your own question.