Search code examples
algorithmoptimizationgraphbipartite

Bipartite graph algorithm

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 ?

Solution

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