1
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Isn't this related to "families of k-independent sets" ? I have no clue over your particular problem. But maybe finding/constructing a family of sets $F$ and then calling the oracle to every element would suffice. $\endgroup$ – seteropere Oct 18 '16 at 6:54
1
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
1
$\begingroup$

If the problem has the property that the decision version can be converted to the search version, it is self reducibility. You can show that all NP-complete problems are self reducible. The idea is to build the instance with the prefix of the verifier for NP-complete problem, and solve it based on the decision version. This is kinda well-known several lines proof.

I am not aware of any other methods to show the fact you asked for.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am pretty confused on how you would actually go about this: "The idea is to build the instance with the prefix of the verifier for NP-complete problem, and solve it based on the decision version." $\endgroup$ – flapdoodle Oct 19 '16 at 3:43
  • $\begingroup$ The first link in Google for the given topic gave me the following : cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf I hope this will help. You are interested in section 2. $\endgroup$ – Eugene Oct 19 '16 at 8:43

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.