1
$\begingroup$

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.

  • 3
    @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.com2011-02-21

1 Answers 1

3

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.