Independent set problem

Question

I'm referring to a post on a black-box algorithm and the 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 = \emptyset$ or $k = 1$, and so we will suppose $V \neq \emptyset$ 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.

---

My question

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?

Answer 1

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.

You have also proved that Independent Set on non-connected graphs is not particularly much easier than on connected graphs.