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

  • 0
    or maybe not ... I'll have to check with a more authoritative source for the problems' definitions.2012-03-06