Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:


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

  • $\begingroup$ @MJD Why are y'all shouting? $\endgroup$ – Řídící Apr 25 '13 at 21:17
  • $\begingroup$ Please reduce your use of caps!!! $\endgroup$ – rschwieb Apr 25 '13 at 21:26
  • 7
    $\begingroup$ It is very common in the literature to write the names of formal problems in all-caps. $\endgroup$ – MJD Apr 25 '13 at 21:58
  • 1
    $\begingroup$ @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. $\endgroup$ – Nick Matteo Apr 26 '13 at 0:24
  • $\begingroup$ Crossposted here. $\endgroup$ – 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?

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.