
Re: [Graph algorithm] Does this problem have a name ?
Posted:
Aug 3, 2011 3:16 PM


On 8/3/11 1:30 PM, candide wrote: > 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 ?
You can transform this from a graph problem to a set problem by providing as input the list of all the skill sets. The set problem is called MINIMUM COVER in Garey and Johnson. It is NPcomplete even if each individual has exactly three skills, and even if we only want to know whether there is an exact cover (a cover in which no skill is duplicated).
Dan

