Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

If P=NP, is there a polynomial-time algorithm $A$ that can decide the $\text{Independent Set}$ decision problem?

That is, with an undirected graph $G = (V, E)$ and a positive integer $k$, does $G$ contain a set of $k$ independent vertices (i.e. a set of vertices no two of which are joined by an edge)?

I am unsure of whether to look at $\text{Independent Set for trees}$ or algorithms that could perhaps solve problems equivalent to $\text{Clique, Vertex Cover}$ etc. in polynomial-time. I would appreciate some guidance on my options and the following development...

Upon choosing $A$, how could I use it to create a further polynomial-time algorithm that finds an $\text{Independent Set}$ of size $k$, rather than just returning a Boolean truth value.

share|cite|improve this question
You might get a faster answer at . – Qiaochu Yuan Feb 21 '11 at 17:47
@Qiaochu_Yuan I appreciated the advice, and acted on it; but after trying to ask this very same question they ridiculed me for not asking something which was post-doctoral research worthy, and even denigrated my understanding of computational complexity. All in all, I won't use ever again. My heart stays with – braedy. Feb 21 '11 at 21:38
up vote 3 down vote accepted

Well, Independent Set is certainly in NP (pick $k$ vertices and check if they form an independent set). So, if P=NP, then yes, there is a polynomial time algorithm for Independent Set.

For your second question, first use $A$ to ensure that there is an independent set of size $k$. Then, remove the first vertex and it's neighbors. Use $A$ to see if the resulting graph has a $k-1$ independent set. If yes, mark the first vertex as in your independent set and recurse. Otherwise, put back everything you took out and try with the second vertex, etc.

That's a really informal sketch, but you get the idea.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.