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.
Best Answer
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.