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.

$\endgroup$
  • $\begingroup$ You might get a faster answer at cstheory.stackexchange.com . $\endgroup$ – Qiaochu Yuan Feb 21 '11 at 17:47
  • 3
    $\begingroup$ @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 $\endgroup$ – braedy. Feb 21 '11 at 21:38
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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