# Induction Proof on Independent Set Variation Algorithm

So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise.

My algorithm is suppose to output impossible if there is no independent set of size k, or output an independent set of size k if it exists.

How might this be approached?

• Forget induction. Can you explain why this algorithm works? – Yuval Filmus May 14 '20 at 6:14
• If the removal of a vertex doesn't remove the possibility of an independent set of size k in the resulting graph, then that vertex is not going to have any affect on the set we are building. That's my intuition for it, or at least what's immediately obvious from running the algorithm on different toy graphs. I guess it's kind of similar to how if there is a graph with an independent set of size k, if I keep adding vertices to the graph, that independent set of size k will remain. – Richard Weng May 14 '20 at 6:19
• Before you can formally prove that the algorithm works, you need to understand why the algorithm works. That's the first step. Make sure that you understand why the algorithm works. – Yuval Filmus May 14 '20 at 8:05
• Right. I'm not quite sure why the algorithm works. I don't understand the implications of what it means for v, when blackbox(G - v, k) says yes or no. Since the graph is constantly being reduced, I just assumed that since it does exist, a set of size k in G, then there are vertices that are part of the set, or that are not part of the set (those that when removed output yes, or those that are neighbor to 1 vertex in the solution. To me, when it returns yes, I understood it as, this vertex makes no difference to the possibility of a set k in G, since G - v doesn't need it. – Richard Weng May 14 '20 at 22:58
• You should concentrate on understanding why this method works. – Yuval Filmus May 15 '20 at 5:51

Let $$G$$ be a graph with an independent set of size $$k$$, and let $$v$$ be an arbitrary vertex. There are two potential types of independent sets of size $$k$$ in $$G$$:

• Independent sets not containing $$v$$: These are independent sets of size $$k$$ in $$G \setminus \{v\}$$.
• Independent sets containing $$v$$: These are formed by adding $$v$$ to independent sets of size $$k-1$$ in $$G \setminus \{v\} \setminus N(v)$$, where $$N(v)$$ is the neighborhood of $$v$$.

Using an oracle for independent set, we can find which of these cases happen.

The basic idea can be implemented in many ways. Here is a recursive implementation, which uses the oracle $$O(G,k)$$, which answers whether $$G$$ contains an independent set of size $$k$$.

• Procedure $$I(G,k)$$
• Input: Graph $$G$$ and integer $$k \geq 1$$
• Output: Independent set of size $$k$$ in $$G$$, or "No" if none exists

1. If $$O(G,k)$$ returns "No", then return "No".
2. Let $$v \in G$$ be arbitrary.
3. If $$k = 1$$, return $$\{v\}$$. Otherwise, continue.
4. If $$O(G \setminus \{v\},k)$$ returns "Yes", return $$I(G \setminus \{v\},k)$$.
5. Otherwise, return $$O(G \setminus \{v\} \setminus N(v),k-1) \cup \{k\}$$.