Name and complexity of this problem on bipartite graphs

Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes.

I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$ contains at least one element and is different from $\hat{V}_{u'}$, $\forall u' \neq u \in U$, where $V_u \subseteq V$ the set of nodes in $V$ to which $u$ is connected.

Note that we can assume that an optimal solution does exist.

To make an example, consider the following graph, with $U=\{A, B, C\}$ and $V=\{X, Y, Z\}$:

The optimal $\hat{V}$ here would be:

Indeed:

• $\hat{V}_{a}=\{x, z\}$

• $\hat{V}_{b}=\{x\}$

• $\hat{V}_{c}=\{z\}$

That is, $\hat{V}$ is the smallest subset of $V$ such that, for every node $u \in U$, $\hat{V}_u$ is non-empty and different from $\hat{V}_{u'} \: \forall u' \neq u \in U$.

This problem definitely rings a bell, but both my memory and my searching skills seem to be failing me. My questions are:

• Does this problem have a name?

• Is it NP-hard and, depending on this answer, can anybody sketch (or point me to) a solution or an approximation?

This problem is related to the hitting set problem. You can represent this problem in terms of sets. Let $V$ be the ground set and we define the family $\mathcal{F} = \{V_u = N_G(u)\colon u \in U\}$

Solutions to your problem have a one to one correspondence with hitting sets $\hat V \subseteq V$ whose intersections with the sets in $\mathcal F$ are pairwise different. The hitting set problem is NP-hard. I am unfamiliar with your version of the problem but you can try to reduce the hitting set problem to your restricted version of the problem to show the hardness of your version as well.

StackExchange Computer Science Q#151518, answer score: 3