# Independent set problem

Question: Suppose that someone gives you a black-box algorithm $$A$$ that takes an undirected graph $$G = (V, E)$$, and a number $$k$$, and behaves as follows.

. If $$G$$ is not connected, it simply returns “$$G$$ is not connected.”

. If $$G$$ is connected and has an independent set of size at least $$k$$, it returns “yes.”

. If $$G$$ is connected and does not have an independent set of size at least $$k$$, it returns “no.”

Suppose that the algorithm $$A$$ runs in time polynomial in the size of $$G$$ and $$k$$.

Show how, using calls to A, you could then solve the Independent Set Problem in polynomial time: Given an arbitrary undirected graph $$G$$, and a number $$k$$, does $$G$$ contain an independent set of size at least $$k$$?

Solution: There are two basic ways to do this. Let $$G = (V, E)$$; we can give the answer without using $$A$$ if $$V = F$$ or $$k = 1$$, and so we will suppose $$V \neq F$$ and $$k > 1$$. The first approach is to add an extra node $$v^*$$ to $$G$$, and join it to each node in $$V$$; let the resulting graph be $$G^*$$. We ask $$A$$ whether $$G^*$$ has an independent set of size at least $$k$$, and return this answer. (Note that the answer will he yes or no, since $$G^*$$ is connected.) Clearly if $$G$$ has an independent set of size at least $$k$$, so does $$G^*$$. But if $$G^*$$ has an independent set of size at least $$k$$, then since $$k > 1$$, $$v*$$ will not be in this set, and so it is also an independent set in $$G$$. Thus (since we’re in the case $$k > 1$$), $$G$$ has an independent set of size at least $$k$$ if and only if $$G*$$ does, and so our answer is correct. Moreover, it takes polynomial time to build $$G*$$ and ask call $$A$$ once.

I think I don't understand the solution(or the question), like I don't understand why it needs to create a new $$G^*$$ to check whether $$G^*$$ has Independent set of size at least $$k$$. I'm thinking naively if algorithm $$A$$ can solve this problem, can't we just input $$G$$ into $$A$$ to get a result?

I'm learning to prove a problem is NP-complete currently, these steps looks like reduction to me. So, whenever we see a problem like given algorithm $$A$$ able to solve a graph problem, we always need to create a new graph $$G^*$$ to verify it?

The reason you can't just take $$G$$ as an input to $$A$$ is that (strangely enough) $$A$$ only works on connected graphs.
You want to prove that if $$A$$ exists, then Independent Set is solvable in polynomial time. The reason you can prove that is by using a polynomial time reduction. You have proved that if $$A$$ exists, then $$A$$ can solve Independent Set on any graph by using your trick of adding a universal vertex.
• Thanks, it makes sense to me now, but referring to the solution, what does $V=F$ mean? – db ddb Dec 9 '19 at 23:22