Markovian Network Interdiction and the Four Color Theorem

The Unreactive Markovian Evader Interdiction Problem (UME) asks to optimally place sensors on a network to detect Markovian motion by one or more "evaders". It was previously proved that finding the optimal sensor placement is NP-hard if the number of evaders is unbounded. Here we show that the problem is NP-hard with just 2 evaders using a connection to coloring of planar graphs. The results suggest that approximation algorithms are needed even in applications where the number of evaders is small. It remains an open problem to determine the complexity of the 1-evader case or to devise efficient algorithms.