Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:
INDEPENDENT SET VALUE
Input: An undirected graph G.
Output:The size of the largest independent set in G (but not the set itself).
Show how you can use this algorithm to solve the INDEPENDENT SET problem in polynomial time: given a graph G, return an independent set which is as large as possible.
Any help would be really appreciated. I am pretty lost in this question
There's a couple of issues to address, first is what definition of INDEPENDENT SET you are using, the "standard" definition is
INDEPENDENT SET (Decision)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Question: Does $G$ have an independent set of size at least $k$?
This is the decision version of the problem, and it should be pretty obvious how to use INDEPENDENT SET VALUE to solve it.
If you however mean the search (or optimization) version of the problem:
INDEPENDENT SET (Search / almost Optimization)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Output: An independent set $I\subseteq V$ where $|I| \geq k$.
If we're looking at the optimization version, then we have the optimization criterion "maximise $k$".
In these cases we can still use INDEPENDENT SET VALUE to solve the problem in polynomial time. What we want is an algorithm that makes a polynomial number of calls to our INDEPENDENT SET VALUE sub-routine, and at each step decides what to do with some element of the graph.
Further hints in spoilers (don't cheat! ;) ):
Say you have a graph $G$ where the size of the largest independent set is $\alpha(G)$ Consider what happens if you delete a vertex from $G$ to get $G'$, then run the INDEPENDENT SET VALUE algorithm on $G'$ - what possible values can you get for $\alpha(G')$, and what does that mean for the vertex you deleted?
