# Is there a name for this bipartite graph problem?

Is there a name for the following problem?

Given a bipartite graph $G = (U,V,E)$:

What is a minimum subset $U'$ of $U$ that covers all of $V$?

(i.e. every vertex of $V$ is connected to at least on vertex of $U'$)

For example, in the graph above, the set $[u_2, u_3]$ (the vertices 2 and 3 of $U$) is a solution.

-

I am not sure if it has got a name in graph theory terms, but you can say it is equivalent to the Set Cover problem.

Given a family of subsets $S = \{S_1, S_2, \dots, S_m\}$ of $\{1,2,\dots, n\}$, you find the smallest subset of $S$ such that the union of those sets is $\{1,2,\dots, n\}$.

You can consider $U=S$, where you represent each vertex by the set of its neighbours and $V=\{1,2,\dots, n\}$.

-
In graph theory terms, the problem is called the "Hitting set problem". –  Gabor Retvari Mar 5 '12 at 22:25
@GaborRetvari: Thanks. But isn't hitting set a non-graph theory term, just like set cover too? –  Aryabhata Mar 5 '12 at 22:32
@Aryabhata, thanks for your answer. The equivalence with Set Cover is very interesting. –  Eelvex Mar 6 '12 at 0:44
@GaborRetvari it seems the "Hitting set problem" is the closest I can get. Why don't you add this as an answer so I can accept it? –  Eelvex Mar 6 '12 at 0:45
@Eelvex: I am not so sure :-) Set cover seems more appropriate. Read this: en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation. –  Aryabhata Mar 6 '12 at 1:01