Problem of finding a very independent set of size at least $k$ is NP-Complete

Question

Given a simple graph $G$, A subset of vertices $V_G$ is called "very independent" if there is no edge between each pair of the vertices in $V_G$ and for each pair $v,v'$, there is no vertex which is connected to both $v$ and $v'$.

In other words, a very independent subset is an independent subset of vertices like $V_G$ such that there is no path of length $2$ or less than it, between each pair of vertices in $V_G$.

How can we prove that the problem of finding a "very independent set" of size at least $k$ in a given simple graph is NP-Complete?

Note: I was thinking of reducing it to the problem of finding an independent set of size $k$... But, Is that even NP-Complete?

Answer 1

Your notion is what is called distance-2 independent sets, also a particular case of rulling sets (see here Independent set where two vertices need to have distance >= c).

Your problem is NP-complete by an easy reduction to Independent Set (which is NP-complete, https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximum_independent_sets_and_maximum_cliques): for every vertex $u,v$ of $G$ such that there exists $w$ with $(u,w) \in E$ and $(v,w) \in E$, add the edge $(u,v)$.

This gives you a new graph $G'$ whose independent sets are the distance-2 independent sets of $G$.