1
$\begingroup$

I was wondering what is the most efficient algorithm to solve something like the following:

You have $P$ people.

You have $T$ tasks, each of which is a set of sets that represent all of the possible sets of people that could be used to complete the task.

What is the minimum set of people required to complete all of the tasks?

For example:

You have $8$ people (call them $1, 2, ...$) and $2$ tasks.

$$T_1 = \{\{1,2\},\{4,5,6\}\}$$ $$T_2 = \{\{7,8\},\{4,5,6\}\}$$

Then the desired result is $\{4,5,6\}$.

I have been trying to think of a few solutions to this, but I'm not convinced any of them are the most efficient way of going about it.

The test case presented above shows that a greedy solution in which the smallest subset in each task is selected does not work as it would result in the set $\{1,2,7,8\}$.

Another possibility is to do a breadth-first search in which you maintain all possible valid subsets while traversing through all of the tasks. But the time complexity of this type of solution would be rather large as you cannot efficiently prune huge valid subsets (such as one containing all $P$ people).

$\endgroup$
  • 1
    $\begingroup$ When all sets in the $T_i$ are singletons, this is set cover, a well-known NP-hard problem. $\endgroup$ – Yuval Filmus Nov 8 '18 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.