Algorithm to determine which neighborhoods of a graph contain a given set of vertices S This question concerns determine which sets in a collection of sets contain a given subset S:

An undirected graph (V,G) is given with V= {1,..,m}, and   given via its neighborhood sets,  N(v_1),.., N(v_m).  A subset S  of V is given {v_{i_1}, .., v_{i_k}}.   The output will be the vertices whose neighborhoods contain S.  The size of the instance is m + |N(v_1)| +…+ |N(v_m)} =n.

Does there exist a linear time algorithm, or an n log n algorithm, or even a sub-quadratic algorithm for this problem?

My naive approach would be remove from set neighborhood set N(v_i) all vertices not in S and count remaining vertices—if |S|, put vertex i  in the output, and if not, do not put vertex i in S. 

I don’t have experience with hash sets (learning on my own)   and don’t really understand why they are so efficient  (self-studying that) but any idea on a quick algorithm would be appreciated.   

-Steve
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.