I'm referring to a post on a black-box algorithm and the Independent Set problem.
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$?
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.
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?