Speaker: Alessandro Maddaloni

Title: Hunting a Rabbit is Hard

Room: P508

Date: June 15

Time: 14:00

Abstract:

In this talk, we consider the Hunters and Rabbit game, where k hunters try to shoot an invisible rabbit on a given graph G. In each round, the hunters shoot at k vertices, while the rabbit moves along an edge of G. The hunters win if they eventually shoot the rabbit. The hunting number h(G) is the smallest k for which k hunters have a winning strategy, regardless of the rabbit’s moves.

The complexity of computing h(G) has been the longest-standing open problem concerning this game, explicitly raised by several authors. We will see that computing h(G) is NP-hard, even for bipartite simple graphs. We will further see that the problem remains NP-hard even when h(G) = O(n^epsilon) or when n - h(G) = O(n^epsilon), where n is the order of G. In addition, we will see that it is NP-hard to approximate h(G) additively within O(n^(1-epsilon)).

We give a forbidden-subgraph characterization of graphs with loops satisfying h(G) = 1, extending a known characterization for simple graphs.

We will finally explore connections with the matrix mortality problem.