# Proving an algorithm exists to find independent set from a graph given an oracle

This is the problem that I have been given:

Consider the Independent-Set problem, in which the input is an undirected graph $G = (V,E)$ and a parameter $k$, and the goal is to determine if $G$ has an independent set of size $k$. Suppose we have an oracle $O$ for solving this decision version of independent set (think of it as a library function that takes input a graph $G$ and $k$ and answers YES/NO). Prove that there exists an algorithm that can find an independent set of size $k$, if one exists, using a polynomial number of calls to the oracle $O$, and possibly a polynomial amount of computation of its own.

My first question is: Is there any way to prove that an algorithm exists without just giving a specific algorithm?

I'm sort of taking a crash course in computer science, so this is not my strongest subject. Any hints as to what direction to take this would be appreciated!

• Isn't this related to "families of k-independent sets" ? I have no clue over your particular problem. But maybe finding/constructing a family of sets $F$ and then calling the oracle to every element would suffice. – seteropere Oct 18 '16 at 6:54

Try running the decision problem subroutine on the original graph $G = (V, E)$. If the answer is NO, clearly you have your answer. If the answer is YES, pick some arbitrary vertex $v \in V$ and remove it from $G$ to produce a new graph $G'$. Now run the decision problem subroutine on $G'$. If the answer is still YES, what did you learn? (This is the "easy" case.) If the answer is now NO, what did you learn? (This case needs a bit more thinking, but not too much.) How many times might you need to repeat this procedure?