# Independent Set decision problem in P

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.

• You might get a faster answer at cstheory.stackexchange.com . – 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 cstheory.stackexchange.com ever again. My heart stays with math.stackexchange.com – braedy. Feb 21 '11 at 21:38

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.