Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a name for the following problem?

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

enter image description here

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.

share|cite|improve this question
up vote 4 down vote accepted

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\}$.

share|cite|improve this answer
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: – Aryabhata Mar 6 '12 at 1:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.