Name and complexity of this problem on bipartite graphs

Question

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?

Answer 1

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.

Answer 2

I don't know a prior result on this particular problem. However, I can show this problem is NP-hard by reducing the hitting set problem.

Suppose we are given an instance of the hitting set problem as a bipartite graph $(U, V, E)$. Let $n = |U|$.

The reduction adds $n$ new vertices to both sides $U' = U \cup \{u_{n+1}, \dots, u_{n+n}\}$ and $V' = V \cup \{v_{n+1}, \dots, v_{n+n}\}$. Then, add edges connecting newly added vertices $E'_1 = \{ (u_{n+i}, v_{n+i}) \mid i \in [n] \}$ and edges connecting original vertices of the left-side and newly added right-side vertices $E'_2 = \{ (u_i, v_{n+i}) \mid i \in [n] \}$ so $E' = E \cup E'_1 \cup E'_2$.

Now, I claim a subset $X \subseteq V$ of the original right vertices is a solution to the original hitting set instance if and only if the subset plus newly-added right vertices $X \cup \{ v_{n+1}, \dots, v_{n+n} \}$ is a solution of the reduced instance $(U',V',E')$ of the problem in the question. A proof sketch follows.

First, because every newly-added left vertex $u_{n+i}$ have only one neighbor $v_{n+i}$, every newly-added right vertex $v_{n+i}$ must be used in the solution.

Second, an original left vertex $u_i$ has a distinct neighborhood set if and only if at least one original neighbor vertex $v_j$ is used in the solution. This is because if no original neighbor vertex is used in the solution, the neighborhood set of $u_i$ is a single newly-added right vertex $\{v_{n+i}\}$ and it is duplicated with the neighborhood set of the newly-added left vertex $u_{n+i}$. Also, no duplication of neighborhood set occurs between original left vertices $u_i, u_j$ because the newly-added right vertex $v_{n+i}$ is only contained in the neighborhood set of $u_i$ if $i \neq j$.