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.

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?


1 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.

  • $\begingroup$ Thanks, it makes sense to me now, but referring to the solution, what does $V=F $ mean? $\endgroup$
    – db ddb
    Dec 9, 2019 at 23:22
  • $\begingroup$ I believe that $F$ is supposed to mean $\emptyset$ and I've updated your post. That's the only thing that makes sense to me. $\endgroup$
    – Pål GD
    Jan 3, 2021 at 19:45
  • $\begingroup$ @dbddb if you feel this answer is useful, feel free to upvote it and even accept it, should it answer your question. $\endgroup$
    – Pål GD
    Jan 3, 2021 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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