Bipartite graph algorithm

Question

Consider the following question relative to graph theory :

Let G a bipartite graph. To make the problem more concrete suppose G is the disjoint union of two sets, say I and S. Suppose

• I represents Individuals with name 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• S represents Skills with name a, b, c, d, e, f, g, h.

So, each individual has some skills, for instance,

• individual 1 has skills b, d, g and h,
• individual 2 has skills a, f, and h,
• etc.

[in the example, datas are randomly given].

We aim to build a team composed of the minimum number of individuals from I in such a way that every skill in S will be represented in the team, that is for each skill s in S, there exists a member of the team having the skill s.

Does this problem have a name ? Does an efficient algorithm for solving it is known ?

Answer 1

Your problem is a minimum set cover problem:

Buy X items from M out of N lots where M is the minimum number of lots you need to obtain all of the X items.

In your example, skills are items and students are lots.

http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml

The problem is NP-hard. The efficient way of solving it is to use the greedy set cover approximation algorithm.

Answer 2

Sounds like a set cover problem
Groups of items from l create a subset of s