Algorithm to determine which neighborhoods of a graph contain a given set of vertices S
In fact, the set of the vertices whose neighborhoods contain S is exactly

$$\bigcap_{j=1}^mN(v_{i_j})$$

Proof:

since it's an undirected graph, $v\in N(u) \Leftrightarrow u\in N(v)$. A vertices $v$ whose neighborhoods contain S means that $\forall u\in S, u\in N(v) $, which is equivalent to $\forall u\in S,v\in N(u)$, thus $\bigcap_{j=1}^mN(v_{i_j})$ is the desire set.

So the problem is equivalent to that:


  Given m (unordered?) lists, get the intersection of them 


One can solve it in $O(n\log n)$ easily by maintain a balanced BST like a std::set.

Or just solve it in $O(n)$ by hashing.