This is an interesting question I'm trying to figure out and I'm really stuck. I need to show that this problem in NP-Hard and reduce it to Independent Set.
The problem is that given a graph where people are represented as nodes and connected with edges to people that they know, find an independent set of people who in addition to not knowing each other, they also do not have shared neighbors in the graph.
Formally, given a graph G=(V,E) and number k, find a set if k vertices in S which are neither joined by an edge nor a path of length 2 in G. I need to prove this is NP-Hard by reduction to Independent Set.