Independent set problem with given black box

Question

I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why.

Suppose that I'm given a polynomial time algorithm $A$ that takes a graph $G=(V,E)$ as input along with integer $k$ and outputs yes if there is an independent set of size atleast $k$, no otherwise. How can I use this algorithm to get an independent set of size atleast $k$ if it exist in polynomial time?

We have $A(G, k) = $ yes if and only if there is an independent set of size atleast $k$. This means if the output is yes, then there is an independent set of size exactly $k$. For a given set of nodes of size $k$, I can verify if it forms an independent set in $O(|E|k)$ time (iterate through the list of edges and ensure that not both ends of an edge lie in my set).

I already know from $A(G,k)$ that there is an independent set of size exactly $k$. Can I check all the subsets of size $k$ if they form an independent set and return the one that does?

There are $|V|\choose k $ $< |V|^k$ subsets of size $k$. According to me, this way, I should be able to get my independent set in $O(|V|^k |E|k)$ which is still polynomial. Could you please tell me if this is correct?

Also, could someone please tell me why such hypothetical problems are discussed? For instance, I know independent set problem is NP Complete and it is suggested by my professor that designers should stop looking for a solution once a problem is proved NP Complete.

Answer 1

No, it is not. "Polynomial time" means "polynomial in the length of the input" (i.e., number of bits needed to represent the input). The length of the input is something like $|V|+|E|+\lg k$, not $|V| + |E| + k$ (assuming $k$ is represented in binary). The running time of your procedure is exponential in the length of $k$ (exponential in $\lg k$), so it is not polynomial time.

The implication of the exercise you're solving is that the task of "find an independent set" is about the same level of difficulty as "check whether an independent set is present (yes/no)" -- it's not much harder. Neither task is likely to have a polynomial time solution. There's not much point looking for an efficient algorithm for either task.