Decycling Graphs and Terrorists
In 2009 I was working at MIT coordinating math research for Research Science Institute for high school students. One of our students Jacob Hurwitz got a project on decycling graphs.
“Decycling” means removing vertices of a graph, so that the resulting graph doesn’t have cycles. The decycling number of a graph is the smallest number of vertices you need to remove.
Decycling is equivalent to finding induced forests in a graph. The set of vertices of the largest induced forest is a complement to the smallest set of vertices you need to remove for decycling.
Among other things, Jacob found induced trees and forests of the highest densities on graphs of all semi-regular tessellations. On the pictures he provided for this essay, you can see an example of a tessellation, a corresponding densest forest, and a corresponding densest tree. The density of the forest and the tree is 2/3, meaning that 1/3 of the vertices are removed.
To motivate RSI students I tried to come up with practical uses for their projects. When I was talking to Jacob about decycling, the only thing I could think of was terrorists. When terrorists create their cells, they need to limit connections among themselves, in order to limit the damage to everyone else in the cell if one of them gets busted.
That means the graph of connections of a terrorist cell is a tree. Suppose there is a group of people that we suspect, and we know the graph of their contacts, then the decycling number of the graph is the number of people that are guaranteed to be innocent.
Have you noticed how Facebook and LinkedIn are reasonably good at suggesting people you might know? The algorithm they use to analyze the data is fairly effective in revealing potential connections. Recently, someone was able to download all of the Facebook data, which means that any government agency ought to be able to do the same thing. They could analyze such data to discover implicit connections. As a byproduct of looking for terrorists, they would also discover all of our grudges.
Oh dear. What are they going to think when they find out I’m not connected to my exes?
Share: