3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Crossposted here. $\endgroup$ – fidbc Apr 26 '13 at 13:04
2
$\begingroup$

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 IS 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 us IS VALUE to solve the problem in polynomial time. What we want is an algorithm that makes a polynomial number of calls to our IS 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 IS VALUE algorithm on $G'$ - what possible values can you get for $\alpha(G')$, and what does that mean for the vertex you deleted?

$\endgroup$

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.