Based on my “extensive” knowledge about police work from binge watching Brooklyn 99, I can conclude that most crimes involve suspects which are narrowed down by detectives to find criminals. These detectives investigate suspects by questioning them and come to a conclusion based on all the evidence they have gathered. So where does graph theory fit into all of this if Jake Peralta can seemingly solve every case that falls upon his lap? Well, it’s possible to significantly reduce the time taken to solve a crime with a few nodes and some basic math. We will consider a simple, but powerful example that displays the topic of discussion.
Jake is stuck on one of his cases and needs YOUR help in figuring out who the criminal is! There has been a fire at a local pizzeria (luckily nobody was injured). Arriving at the crime scene, Jake concludes this was an arson and gathers witness reports to understand more about the crime. After conducting a brief investigation, he comes to the conclusion that one of the owner’s of local competing pizzerias is responsible for the arson. The owners of these pizzerias are – Aidan, Brandon, Clara and David. Jake begins interrogating these four suspects. The following are their statements:
- Aidan: “I did not commit the crime”
- Brandon: “Aidan committed the crime”
- Clara: “Brandon committed the crime”
- David: “I did not commit the crime”
Jake is confused and has no clue who the real arsonist is. Let’s use some basic graph theory to help him out.
When suspect X says that he/she did not commit the crime, he/she is implying one of the other suspects committed the crime. Aidan states that he did not commit the crime. Hence, he is implying that it was either Brandon, Clara or David. So let’s draw a directed edge from Aidan to every other suspect. Now, Brandon claims that Aidan committed the crime. Therefore, we draw a directed edge from Brandon to Aidan, implying Brandon is accusing Aidan. We do the same with Clara and David to come to the graph depicted in the picture above. Now, based on the interrogations, we can clearly see that not everyone is telling the truth. Let’s assume that there is only one criminal and out of all the suspects, only one is telling the truth (we will see why later).
Hypothesis: Aidan is the criminal
Let’s assume Aidan is the criminal. This implies that Brandon, Clara and David did not commit the crime. We also know that only one suspect is telling the truth (based on our assumption). Hence, looking at their statements, Aidan is lying when he says he’s not the criminal, Brandon is telling the truth when he says Aidan is the criminal, Clara is lying when she says Brandon is the criminal and David is telling the truth that he did not commit the crime. However, we can see that 2 suspects are telling the truth which is a contradiction to our assumption (only one person is telling the truth). Hence, Aidan is not the criminal.
Hypothesis: Brandon is the criminal
Let’s assume that Brandon is the criminal. Therefore, Aidan is telling the truth when he says he’s not the criminal, Brandon is lying when he says Aidan is the criminal, Clara is telling the truth when she says Brandon is the criminal and David is telling the truth when he says he’s not the criminal. Here, 3 suspects are telling the truth which is a contradiction to our assumption that only one person is telling the truth. Hence, Brandon is not the criminal either.
Hypothesis: Clara is the criminal
Let’s assume that Clara is the criminal. Therefore, Aidan is telling the truth when he says he’s not the criminal, Brandon is lying when he says Aidan is the criminal, Clara is lying when she says Brandon is the criminal and David is telling the truth that he’s not the criminal. Here too, we see that 2 suspects are telling the truth which is a contradiction to our assumption that only one person is telling the truth. Hence, Clara is not the criminal.
Hypothesis: David is the criminal
Let’s assume that David is the criminal. Therefore, Aidan is telling the truth when he says he’s not the criminal, Brandon is lying when he says Aidan is the criminal, Clara is lying when she says Brandon is the criminal and David is also lying when he says he’s not the criminal. We can see here that only Aidan is telling the truth that satisfies our original assumption that only one suspect is telling the truth. Hence, David is the criminal!
Now comes the interesting part!
To simplify this entire process, we just need to look at the graph of each hypothesis and find the In-degree of the suspect node we are considering for that hypothesis. The In-degree of suspect X would clearly indicate the number of suspects telling the truth when X is the criminal. In the above example, we arrive at the final set: (2, 3, 2, 1) which is the in-degree of nodes (A, B, C, D) respectively, indicating the number of suspects telling the truth when that suspect node is the criminal (which is what we derived earlier). This is extremely powerful! Now, if we knew that two people were telling the truth, we would simply need to look at this set (2, 3, 2, 1) to find out who is the criminal and see that Aidan or Clara or both would be criminals! Similarly, if we knew that 3 suspects were telling the truth, we can conclude that Brandon is the criminal!
Conclusion
In real life cases, it’s not always possible to tell how many suspects are telling the truth (fake alibis etc). But look at how powerful this is. If we had a list of 10, 20 and maybe even 30 suspects, it is possible to significantly narrow down this list of suspects. In fact, advance modifications of such ideas are used indeed used in solving crimes. To conclude, although graph theory can’t replace the work of an actual detective, it can surely make his/her life much easier and provide critical information that is otherwise very hard to see.
Reference:
https://www.ijrte.org/wp-content/uploads/papers/v8i6/F9355038620.pdf