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.