Which algorithm can rationally reduce multiple lists? ("who killed who" pro​blem)

Question

I do not know if the problem I am talking about has a name, if that is the case, I would like to know it in order to do more research.

To explain my problem, it is easier to visualize it.

I will give a representation but many others have been possible.

• In a small town, the police found a large number of corpses.
• For each corpse found, there is a number of suspects among the inhabitants of the city.
• A murderer can not kill more than one person.
• There is a solution.
  
  Find out who killed who!

As I write this, I realize that there may have many variants of this problem, so it would be really useful to know what kind of problem it is.

---

I will use a test game.
So for each corpse, we have a set of suspect among the inhabitants.

C1 -> [S1, S3]
C2 -> [S1, S3, S4]
C3 -> [S2]
C4 -> [S2, S3]

By logical deduction, it is then easy to determine who killed who.

1. There is only one suspect for C3, so, S2 is the murderer.
2. S2 is the murderer of C3, so he can not be the murderer of C4. This means that S2 killed C4.
3. S1 is the latest potential suspect for C1, so he is the murderer.
4. Finally, S4 is the murderer of C2.

Which gives us the solution:

C1 -> S1
C2 -> S4
C3 -> S2
C4 -> S3

A naive implementation of the algorithm to solve this would be:

found = []

for corpse in corpses:
    corpse.suspects = [s for s in corpse.suspsects if s not in found]
    if len(corpse.suspects) == 1:
        found.append(suspects[0])
        continue # Restart the loop to remove the new killer found 
                 # from previous corpses suspects

The problem is that it becomes very expensive with a large number of bodies and suspects, the loop takes a long time. Of course, small improvements are possible (remove the body from the list once the suspect found, for example) but the algorithm seems to me still not optimal.

Is there a better algorithm for this problem? And I repeat again, is it a specific name for this kind of problem? It could definitely help me a lot.

Answer 1

This is an example of a maximum bipartite matching. The bipartite graph in question is defined by the two sets of people (corpses and suspects) and the edges linking each corpse to the suspects who might have killed him. A maximum matching will choose one edge per corpse (where possible) without choosing more than one edge per suspect.