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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.