Abstract: Consider a game where an intruder is hiding in a node in an undirected graph. At each iteration, you are allowed to inspect k nodes of the graph to see if the intruder is in one of them. If the intruder is not caught, it moves to an adjacent node. The intruder wins if he can escape forever. We consider the question of, given a graph and a number k (where k is the number of nodes that you can inspect at each iteration) whether an optimal intruder can escape forever. We review some of the known results for the special cases of k=1 and when G is a tree, and then show that the general case is NP-hard.
Joint work with Juan Jose Besa, Siddharth Gupta, Elham Havvaee, Timothy U. Johnson, Jordan Jorgensen, Tung Mai, Pedro Matias, and Martha Osegueda