# Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a general graph can be determined using an algorithm designed for 3-colorable graphs.

Construction Approach: Given a graph $$G=(V, E)$$, I construct a new graph $$G'$$ by modifying each edge $$e \in E$$. For an edge $$e=(u, v)$$, I introduce two new vertices $$w_e$$ and $$x_e$$. The edge $$(u, v)$$ is then replaced with a path $$u - w_e - x_e - v$$.

Coloring Argument: Graph $$G'$$ can be shown to be 3-colorable. By coloring the original vertices from $$G$$ with color 1, and alternating the colors 2 and 3 for the newly added vertices on each edge, a valid 3-coloring for $$G'$$ is achieved.

Question: Assuming we have determined the size of the maximal independent set in the 3-colorable graph $$G'$$, how can we utilize this information to find the size of the maximal independent set in the original graph $$G$$?

I find myself at an impasse with this question. The strategy for constructing $$G′$$ was suggested by my instructor, and I have followed it to the best of my understanding. However, I am still seeking clarity on how to proceed further. Any guidance or insights provided would be immensely appreciated!

• Just clarifying that you need a maximal (not maximum) independent set, right? Commented Jun 4 at 8:50
• @codeR Yes. Telling maximal is the correct way to say that. Commented Jun 4 at 12:02

Suppose we find a maximal independent set for $$G'$$ and let it be $$I'$$. We will now prune $$I'$$ so that it becomes an independent set of $$G$$. For each edge $$(u,v)$$ in the origianl graph $$G$$, we may have exactly two vertices among $$\{u,v,w_e,x_e\}$$ in $$I'$$. More specifically, we can have either $$\{u,x_e\} \in I'$$ or $$\{v,w_e\} \in I'$$ or $$\{u,v\} \in I'$$. For the first two cases, we can simply delete either $$w_e$$ or $$x_e$$. For the case $$\{u,v\} \in I'$$, we have to delete either $$u$$ or $$v$$ in order to make it an independent set of $$G$$. Here, we can apply any greedy criterion, such as deleting the one with highest degree in $$G$$. At the end of this iterative deletion, we will be left with a maximal independent set of $$G$$.
• Thanks for your answer. I greatly appreciate it. But how can I prove that this greedy criterion will lead to the maximal independent set in $G$? Being an independent set is easy to show, but how about being maximal? Commented Jun 4 at 14:09
• For every pair of vertices $u$ and $v$, you only delete one of them if $(u,v)$ is in $G$. Thus you can not add the deleted ones back. Hence the final independent set $I'$ is maximal. Commented Jun 5 at 7:50