On sabotage games

Hosted by Andy McLennan

Sabotage games on a graph involve Runner who wants to travel between two given vertices and Blocker who aims to prevent Runner from arriving at his destination by destroying edges. This paper introduces and studies several generalizations of sabotage games.

First, it completely characterizes games with multiple destinations on weighted trees for both local and global cutting rules of arbitrary capacity, using an algorithmic labeling procedure.

Second, it introduces the transformation procedure that associates a weighted tree with any weighted graph. The procedure allows complete characterization of games on weighted graphs for local cutting rules of arbitrary capacity and provides sufficient conditions for Blocker to win for global cutting rules.

The applications of sabotage games to the issue of border security are discussed.