# How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

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

• @MJD Why are y'all shouting? – Řídící Apr 25 '13 at 21:17
• Please reduce your use of caps!!! – rschwieb Apr 25 '13 at 21:26
• It is very common in the literature to write the names of formal problems in all-caps. – MJD Apr 25 '13 at 21:58
• @rschwieb and Gugg: An independent set is a set of vertices with no edges among them. INDEPENDENT SET is the problem of finding an independent set of maximum size in a given graph. It make sense to discuss the time complexity of the latter, but not the former. – Nick Matteo Apr 26 '13 at 0:24
• Crossposted here. – fidbc Apr 26 '13 at 13:04

Hint: Suppose you run INDEPENDENT SET VALUE on $G$ and get $n$. Then you delete a vertex from $G$ to get $G'$ and run INDEPENDENT SET VALUE on G'. What are the possible results? What might you learn from each of the possible results?