TL;DR
This paper introduces a "monotone" variant of the classic Hunters and Rabbit pursuit-evasion game, showing that this constraint can significantly alter game dynamics and computational complexity. They establish a tight relationship between this monotone hunter number and pathwidth, proving NP-hardness for general graphs while developing polynomial-time algorithms for specific graph classes like trees and cographs.
What Problem Does This Paper Address?
The Hunters and Rabbit game is a classic pursuit-evasion puzzle played on a graph. One player (Hunter) tries to capture an invisible player (Rabbit) by shooting at vertices. The Rabbit wins if it can evade capture indefinitely. The "hunter number" of a graph is the minimum number of hunters needed for the Hunter to guarantee a win. While this game has been studied extensively, its computational complexity remains an open problem, even for restricted graph classes like trees. This paper addresses this by introducing a "monotonicity" constraint to the game. In classical graph searching games, monotonicity means searchers don't revisit already "cleared" areas. The authors adapt this concept to the Hunters and Rabbit game, where a cleared vertex cannot be "recontaminated" by the Rabbit. This new variant, the "monotone hunter number," allows them to derive new theoretical results and develop efficient algorithms for specific graph types.
Methods
The core of this paper lies in introducing and analyzing the "monotone hunter number" ($mh(G)$) of a graph $G$. They define monotonicity in the context of the Hunters and Rabbit game, where a vertex, once "cleared" (either by being shot or by its neighbors being cleared), must be shot again if the Rabbit can potentially reach it.
Key methodological contributions include:
- Formalizing Monotonicity: Adapting the concept of monotonicity from classical graph searching games to the specific rules of the Hunters and Rabbit game.
- Relating $mh(G)$ to Pathwidth: Proving a fundamental result: $pw(G) \le mh(G) \le pw(G) + 1$ for any graph $G$, where $pw(G)$ is the pathwidth. This immediately implies that computing $mh(G)$ is NP-hard.
- Developing Polynomial-Time Algorithms: For specific graph classes (split graphs, interval graphs, cographs, and trees), they develop efficient algorithms to compute $mh(G)$. These algorithms often leverage structural properties of these graph classes and existing algorithms for related problems (like pathwidth computation).
- Analyzing the "Red Variant": Investigating a restricted version of the game on bipartite graphs where the Rabbit must start in a specific partition of vertices. This analysis reveals scenarios where monotonicity can be detrimental, leading to larger gaps between the standard and monotone hunter numbers.
- Kernelization for Parameterized Complexity: They show that the problem of deciding $h(G) \le k$ or $mh(G) \le k$ is fixed-parameter tractable (FPT) when parameterized by the vertex cover number of the graph, by providing a kernelization algorithm.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Monotonicity Changes the Game: The introduction of monotonicity significantly alters the game's dynamics. While in some pursuit-evasion games monotonicity simplifies strategies, here it can sometimes increase the required number of hunters, leading to a gap between the standard hunter number ($h(G)$) and the monotone hunter number ($mh(G)$).
- Tight Link to Pathwidth: The $pw(G) \le mh(G) \le pw(G) + 1$ result is a major theoretical contribution. It connects a game-theoretic concept directly to a well-studied graph parameter, providing a powerful tool for analysis and complexity classification.
- NP-Hardness for General Graphs: The tight link to pathwidth immediately establishes that computing $mh(G)$ is NP-hard, a significant complexity result.
- Algorithmic Tractability in Specific Classes: Despite the general NP-hardness, the paper demonstrates that $mh(G)$ can be computed efficiently for important graph classes like trees, cographs, and split graphs. This highlights the importance of graph structure in algorithmic game theory.
- "Recontamination Helps": The paper shows that for the standard Hunters and Rabbit game, $h(G)$ can be arbitrarily smaller than $mh(G)$. This means that allowing the Rabbit to "recontaminate" previously cleared areas can be a significant advantage for the Rabbit, making it easier for the Hunter to win with fewer hunters in the standard game.
Key Results
- Complexity of $mh(G)$: For any graph $G$, $pw(G) \le mh(G) \le pw(G) + 1$. This implies that computing $mh(G)$ is NP-hard.
- Polynomial-Time Algorithms: $mh(G)$ can be computed in polynomial time for:
- Split graphs (characterizing $mh(G)$ based on clique size).
- Interval graphs (relating $mh(G)$ to clique number).
- Cographs (linear time algorithm based on recursive decomposition).
- Trees (polynomial-time algorithm using dynamic programming based on a novel "Parsons-like" lemma).
- FPT Parameterized by Vertex Cover: The problem of deciding $h(G) \le k$ and $mh(G) \le k$ is FPT when parameterized by the vertex cover number, with a kernel of size $O(4^{vc(G)})$.
- Gap between $h(G)$ and $mh(G)$: The paper demonstrates that the gap between $h(G)$ and $mh(G)$ can be arbitrarily large, meaning recontamination can be highly beneficial for the Rabbit.
Limitations and Future Work
- Complexity of $h(G)$: The computational complexity of the standard hunter number $h(G)$ remains an open problem, even for trees. The paper suggests that their monotonicity-based approach might not be sufficient to solve this.
- Parameterization: While $mh(G)$ is shown to be FPT parameterized by vertex cover, the paper suggests exploring other parameters like treewidth and pathwidth for both $h(G)$ and $mh(G)$.
- Specific Graph Classes: The paper poses open questions about computing $h(G)$ for various graph classes, including trees, cographs, and interval graphs.
- Grids: The monotone hunter number of grids is mentioned as an interesting open problem.
- New Tools for $h(G)$: The paper's findings imply that a direct application of monotonicity might not solve the $h(G)$ problem for trees, suggesting the need for novel techniques.
Summary updated