Spanish Juggling problem

These are some notes to be shared about a specific kind of problem I am thinking about since yesterday.

Problem formulation

You are given a list of persons P, a list of capabilities (or skills) C, and a list of all the capabilities per person. A person can have any number of capabilities. For each capability, there is at least one person who possesses it. Find the smallest set of persons so that they, in total, have all capabilities.

(Optional:) If there are multiple possible smallest sets, find them all.

Example 1

You are given the following data.

Persons:

• P1: Sri
• P2: Yuan
• P3: Kim
• P4: Elias

Capabilities:

• C1: Juggle
• C2: Speak Spanish
• C3: Do a handstand
• C4: Solve differential equations

Capabilities per person:

• Sri (P1) can juggle (C1)
• Yuan (P2) can do a handstand (C3)
• Kim (P3) can speak Spanish (C2) and solve differential equations (C4)
• Elias (P4) can do none of the above

Solution:

To have all four capabilities, the first three persons are needed (Sri, Yuan, and Kim). There is no alternative solution.

Example 2

The data changes to the following.

Persons:

• P1: Pia
• P2: Elise
• P3: Ashwin
• P4: Martha
• P5: Nardole

Capabilities:

• C1: Play the piano
• C2: Solve a Rubik’s cube in 60 seconds
• C3: Moonwalk
• C4: Do the Heimlich maneuver
• C5: Understand Morse code

Capabilities per person:

• P1: C2, C4
• P2: C1
• P3: C3, C4
• P4: C2, C5
• P5: C1, C2, C4

Solution:

This example is not quite as obvious. To get a better overview, we can create a “capability matrix” with all persons:

   C1 C2 C3 C4 C5
P1    xx    xx
P2 xx
P3       xx xx
P4    xx       xx
P5 xx xx    xx

Because Ashwin (P3) is the only one who can moonwalk (C3) and Martha (P4) is the only one who can understand Morse code (C5), they are always needed in the solution set. Those two together already have skills C2, C3, C4, and C5. As Elise (P2) and Nardole (P5) are the only ones who can play the piano, one of them can be chosen to get to an optimal solution. The two possible smallest sets of persons are therefore (sorry, Pia):

• Elise, Ashwin, Martha (P2, P3, P4)
• Ashwin, Martha, Nardole (P3, P4, P5)

Application

A solution for this issue might not only be helpful when trying to have a fun evening but also came up when trying to find the smallest set of Code Owners (which must approve specific files) necessary in a Code Review.

As a graph problem

One possible way to look at the problem might be as follows: Create one vertex per person and one per capability. Create a source vertex and connect it to all person vertices with weight 1. Connect the person vertices to each capability vertex for which they have the capability. At last, find the tree of minimum weight that contains all capability vertices. The graph in the case of Example 2 might look like this:

This way of formulating the issue is a Steiner tree problem which seems not to be solvable in polynomial time for the general case. Maybe this variant can be, though? There also seem to be some approximations.

As an Integer Program

It should also be possible to express this problem with Integer Linear Programming (ILP). Each person might correspond to one decision variable (yes/no), the count of chosen persons should be minimized, and each capability could correspond to a constraint: The count of all chosen persons who have this capability must be greater than 0. The problem would still be NP-hard but finding the actual solution could be outsourced to a solver.

Constraints

• The number of persons plus the number of capabilities is usually below 200
• The optimal solution (w.r.t. the number of persons) would be nice but is not strictly necessary