In the Hunters and Rabbit game, $k$ hunters attempt to shoot an invisible rabbit on a given graph $G$. In each round, the hunters select $k$ vertices to shoot at, while the rabbit moves along an edge of $G$. The hunters win if, at any point, the rabbit is shot. The hunting number of $G$, denoted $h(G)$, is the minimum integer $k$ such that $k$ hunters have a winning strategy regardless of the rabbit's moves. The computational complexity of determining $h(G)$ has been one of the longest-standing open questions about the game. Our first main contribution resolves this by proving that computing $h(G)$ is NP-hard, even for bipartite simple graphs. We further show that the problem remains NP-hard even when $h(G) = O(n^ε)$ or when $n - h(G) = O(n^ε)$, where $n$ is the order of $G$. In addition, we prove that it is NP-hard to approximate $h(G)$ additively within $O(n^{1-ε})$. When a time limit $l$ is imposed on the hunting process, we show that computing $h(G)$ remains NP-hard for any $l \ge 2$ bounded by a polynomial in $n$. On the positive side, we present a polynomial-time $l$-factor approximation algorithm for computing the hunting number with time limit $l$, and we show that $h(G)$ can be computed in polynomial time for bipartite graphs when only two time slots are allowed ($l = 2$). Finally, we provide a forbidden-subgraph characterization of graphs with loops that satisfy $h(G) = 1$, extending a known characterization for simple graphs.

翻译：在猎人与兔子游戏中，$k$ 名猎人试图在给定图 $G$ 上射杀一只不可见的兔子。每轮中，猎人选择 $k$ 个顶点进行射击，而兔子则沿 $G$ 的一条边移动。若兔子在任意时刻被击中，则猎人获胜。图 $G$ 的追捕数记为 $h(G)$，表示无论兔子如何移动，$k$ 名猎人拥有必胜策略的最小整数 $k$。确定 $h(G)$ 的计算复杂性一直是该游戏中最长期未决的问题之一。我们的第一个主要贡献通过证明计算 $h(G)$ 是 NP 难的（即使对于二分简单图）解决了这一问题。我们进一步证明，即使当 $h(G) = O(n^ε)$ 或 $n - h(G) = O(n^ε)$（其中 $n$ 为 $G$ 的阶数）时，该问题仍然是 NP 难的。此外，我们证明了在 $O(n^{1-ε})$ 的加法误差范围内近似 $h(G)$ 也是 NP 难的。当对追捕过程施加时间限制 $l$ 时，我们证明对于任何 $l \ge 2$ 且 $l$ 为 $n$ 的多项式有界时，计算 $h(G)$ 仍然是 NP 难的。在积极方面，我们提出了一个多项式时间的 $l$ 因子近似算法，用于计算具有时间限制 $l$ 的追捕数，并证明当仅允许两个时间槽（$l = 2$）时，二分图的 $h(G)$ 可在多项式时间内计算。最后，我们通过禁止子图特征刻画了满足 $h(G) = 1$ 的带环图，扩展了简单图的已知特征刻画。