The Minimum Cut problem motivated some of the earliest work in operations research. Recently problems like MinCut became important because of the threat of terrorism. One such variant is termed Markovian Network Interdiction (MNI). In MNI an adversary moves stochastically towards a target in the network, and the objective is to best "interdict" him by placing sensors. MNI is shown to be NP-hard to solve (through a surprising connection to the Four Color Theorem). To address the complexity, we developed an approximation algorithm that can compute network interdiction solutions on the global scale. We have also identified international conflicts of interest that will arise from deploying such systems.