Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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: en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation. –  Aryabhata Mar 6 '12 at 1:01
show 2 more comments

Your Answer

 
discard

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.