Suppose a wildfire starts in a forest (like in the Amazon rainforest) and you have a limited amount of resources to fight the fire as it spreads throughout the forest. What is the best strategy you should deploy so that you can maximize the number of trees you save before the fire is distinguished?
This is the so-called Fire Fighter Problem, it has been discovered since 1995 and is still studied and experimented till today. It’s easy to see that we can transform the description of this problem into a network where
- nodes = trees in the forest
- edges = exists if a tree is next to another
- S = the sources of the fire
- Strategy = the way in which “firefighters” are deployed to fight the fire
and the goal would be to save the largest set of trees in the forest.
A keen student might attempt to solve this optimization problem with techniques we learn(ed) in CSCB63 and CSCC73. However, it turns out that the Fire Fighter Problem is a NP-hard problem, which means that we have not yet figured out an efficient solution that can deterministically solve every instance of this problem (without proving P=NP first!).
In my opinion, this result actually have a huge significance in our lives. If we refer to our classmate Sol and Jayden‘s blog posts — Sol investigated on the disease spreading network and Jayden on the computer virus network. Both of their problems can be seen as analogous to the Fire Fighter Problem. This implies that it is mathematically hard to come up with a very efficient algorithm to vaccinate people in a network or come up with a protocol to prevent a large network (maybe a SCC in the web) from being infected by a virus or malware.
From Netflix’s “Inside Bill’s Brain” documentary, Bill Gates talked about how it was extremely difficult to exterminate Polio in Africa as figuring out an efficient vaccination strategy was hard. Although this is unfortunate, it is not surprising from our insight of the Fire Fighter Problem and further confirms our intuition on this family of problems.
In summary, we see how we can describe a real world problem into one that involves networks, and by understanding from mathematical results, we can infer how difficult it is to implement a strategy in a real world system.
References:
If we consider the problem in the aspect of stopping the fire to prevent spreading, similarly to the idea of flow, where parts of the fire is spread to nearby trees, is there a “fast-enough” algorithm to select the best trees to save which prevents the fire from spreading?
That’s an interesting thought, yes this variation of the problem is still hard to solve, though we have some greedy approximation algorithm that will yield not the most optimal but “close-to-optimal” solutions. You can refer to https://www.mathstat.dal.ca/~cduffy/DuffyMSc.pdf for some important results from all variations of the firefighter problem.