World's most popular travel blog for travel bloggers.

[Solved]: Proving an algorithm exists to find independent set from a graph given an oracle

, , No Comments
Problem Detail: 

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!

Asked By : flapdoodle

Answered By : j_random_hacker

Here's a hint.

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?

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback