# Independent set poly reducible to Strongly independent set?

A strongly independent set of a graph $$G'$$ is a subset $$S$$ of vertices such that the distance in $$G'$$ between every two distinct vertices in $$S$$ is larger than $$2$$.

It is possible to reduce an instance $$\langle G, k\rangle$$ of the decision version of independent set to an instance $$\langle G', k\rangle$$ of the decision version of strongly interdependent set by (1) replacing each edge $$e=(u,v)$$ of $$G$$ with two edges $$(u, w_e)$$ and $$(w_e, v)$$, where $$w_e$$ is a new vertex; and (2) connecting all the vertices $$w_e$$ with a clique.

In the newly created Graph $$G'$$, why does adding a middle node prevent us from choosing that node? Basically, how does the reduction step help us?

Solution Notes: http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut11.pdf

• Welcome to StackExchance. I added some more context to your question. Please try to post self-contained questions in the future. – Steven Apr 30 at 11:27

Assume that the integer $$k$$ of the (decision version of the) independent set instance $$G$$ you are reducing from is larger than $$1$$ (the case $$k \le 1$$ is trivial). Let $$G'$$ be the graph of the corresponding instance of strongly independent set.
As it is written in your solution notes, all the additional vertices are connected to one another with a clique. If you select any of them, say $$w_e$$, then you cannot select any other vertex $$v$$ in $$G'$$ since the distance in $$G'$$ between $$v$$ and $$w_e$$ is at most $$2$$. This implies that the size of a maximum strongly independent set of $$G'$$ is $$1$$. Therefore, if there is a strongly independent set of $$G'$$ of size $$k$$, it must not include any vertex $$w_e$$.
• If $$S$$ is an independent set for $$G$$, then $$S$$ is also a strongly independent set for $$G'$$ since all pairs vertices in $$S$$ are at a distance of at least $$2$$ in $$G$$ and hence they are at distance of at least $$4$$ in $$G'$$.
• If $$S$$ is a strongly independent set for $$G'$$ with $$|S| \ge k$$, then $$S$$ cannot include any vertex $$w_e$$, and is therefore a subset of the vertices of $$G$$. The distance between any two distinct vertices in $$S$$ is larger than $$2$$ in $$G'$$, and hence it is larger than $$1$$ in $$G$$.
• The graph is unweighted (or, if you prefer, all edges cost $1$). – Steven Apr 30 at 16:56