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

  • $\begingroup$ Welcome to StackExchance. I added some more context to your question. Please try to post self-contained questions in the future. $\endgroup$ – 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$.

The correctness of the reduction is then easy to see:

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

| cite | improve this answer | |
  • $\begingroup$ Is the edge cost between a node v and we 2? $\endgroup$ – JohnySmith12 Apr 30 at 16:48
  • $\begingroup$ The graph is unweighted (or, if you prefer, all edges cost $1$). $\endgroup$ – Steven Apr 30 at 16:56

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.