# Independent Set Problem Variant, Induction

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.

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$$.

• 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. – Richard Weng May 13 at 7:49
• @RichardWeng What exactly was wrong with $K_3$ (triangle) with $k=1$? – ljeabmreosn May 13 at 8:00
• I'm curious, what is the intuition for why this works? Because I can't seem to see why it works. – Richard Weng May 13 at 20:00
• 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. – Richard Weng May 13 at 20:21
• 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. – Pål GD May 14 at 6:44