4
$\begingroup$

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.

1 Answers 1

4

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

  • 1
    In graph theory terms, the problem is called the "Hitting set problem".2012-03-05
  • 0
    @GaborRetvari: Thanks. But isn't hitting set a non-graph theory term, just like set cover too?2012-03-05
  • 0
    @Aryabhata, thanks for your answer. The equivalence with Set Cover is very interesting.2012-03-06
  • 0
    @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?2012-03-06
  • 0
    @Eelvex: I am not so sure :-) Set cover seems more appropriate. Read this: http://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation.2012-03-06
  • 0
    @Aryabhata as a *name* the "Set Cover" is more general so the "Hitting Set" seems more appropriate for my case.2012-03-06
  • 0
    or maybe not ... I'll have to check with a more authoritative source for the problems' definitions.2012-03-06