0
$\begingroup$

So the question gives us some mysterious algorithm, that given a graph G and an integer k, it outputs true/false to whether there is an independent set of size k in G.

So we have to design an algorithm that can call this mysterious algorithm within a polynomial number of times, to return an independent set of size k from G if it exists, or outputs impossible. The hint is induction.

I'm having trouble figuring an algorithm to solve this. I know however, that the proof for this algorithm involves removing or adding a vertex in the inductive step.

$\endgroup$
2
$\begingroup$

Hint: Suppose you have a graph $G = (V,E)$ which is yes, and then there is a vertex $v \in V$ such that $G - v$ (the graph where you have removed $v$ from the graph) is no. What can you say about $v$ and $G$?

Let us take an example, namely the following graph:

$G= (\{a,b,c,d\}, E=\{ab, bc, cd, ad, ac\})$

a —— d
| \  |
|  \ |
b —— c

and with $k=2$. This is currently a yes instance.

First we ask: If we delete $a$ from $G$, will the resulting instance still be a yes instance?

     d
     |
     |
b —— c

The answer is yes, this graph is still a yes instance.

Then we delete $b$ and ask the same question:

     d
     |
     |
     c

The answer is now no, this instance is no longer a yes instance. Hence we cannot delete $b$. Instead we try to delete $c$:

     d


b     

The answer is still yes, and $|V(G')| = k$, so we conclude that $\{b, d\}$ is an independent set in $G$ of size $k$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So I tried seeing if v is a vertex in the independent set. A toy example of 4 vertices connected in a square shape, with 1 edge diagonally through the middle, and searching for an independent set of size 2. When I removed a vertex that was previously part of the independent set, the resulting graph would return no, but yes for a removal of a non-independent set vertex. But then with a triangular graph on 3 vertices and k=1, the idea doesn't quite hold. I'm not sure if I am having a correct train of thought. $\endgroup$ – Richard Weng May 13 at 7:49
  • $\begingroup$ @RichardWeng What exactly was wrong with $K_3$ (triangle) with $k=1$? $\endgroup$ – ljeabmreosn May 13 at 8:00
  • $\begingroup$ I'm curious, what is the intuition for why this works? Because I can't seem to see why it works. $\endgroup$ – Richard Weng May 13 at 20:00
  • $\begingroup$ Oh I see, we have to remove all of v's neighbors as well in our induction if v is a candidate for the set. $\endgroup$ – Richard Weng May 13 at 20:21
  • $\begingroup$ Well, this is the way you construct a solution from the decision problem. I don't know how to explain why it works, you just need to play around with examples, and maybe try to write a formal proof for it. And obviously you have an oracle for the decision problem, so it's not something that normally works in polynomial time. $\endgroup$ – Pål GD May 14 at 6:44

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.