Source-linked AI summary
PSPACE-completeness of the Hunters and Rabbit game
Walid Ben-Ameur, Alessandro Maddaloni
TL;DR
The paper addresses whether Hunters and Rabbit capture is PSPACE-complete, including on simple bipartite graphs. It reduces common-word acceptance for inverse finite automata to winning strategies and establishes PSPACE-completeness for the ordinary game and related variants.
Problem
Whether the ordinary Hunters and Rabbit decision problem is PSPACE-complete remained open despite known PSPACE membership and prior NP-hardness.
Source: §1 · p. 2Method
The reduction encodes inverse finite automata so that guards and a safe-haven clique force winning strategies to simulate common transitions and test accepting tuples.
Source: §3.1 · p. 7Results
The problem is PSPACE-complete for simple bipartite graphs, for the directed game with one hunter on oriented graphs of positive minimum outdegree, and for firefighting on simple undirected graphs.
Source: §1 · p. 4, §3.2 · p. 14, §3.3 · p. 15Takeaways & Limitations
The classification covers the ordinary game under a simple bipartite restriction and also extends to directed one-hunter and firefighting variants.
Source: §1 · p. 4, §3.2 · p. 14, §3.3 · p. 15The hardness constructions use graphs without isolated vertices, and the resulting digraphs have positive minimum outdegree.
Source: §2 · p. 5
Abstract
from arXiv · showhide
In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.
1. Introduction
The paper resolves whether deciding if a given number of hunters can guarantee capture is PSPACE-complete, proving hardness even for simple bipartite graphs. It reduces inverse finite-automata intersection nonemptiness to the game and extends the classification to directed and firefighting variants.
1. Introduction
- Earlier Hunters and Rabbit work solved the one-hunter undirected case and established structural and algorithmic results for multiple hunters [3] [4].Results include bounds involving pathwidth and hunting numbers for grids, trees, and hypercubes.Source: §1 · p. 2
- Monotone hunting can require more hunters than ordinary hunting: for every r ≥ 3, some tree T has h(T) = 2 and mh(T) = r [6].Thus, monotone strategies alone do not capture the ordinary game's complexity.Source: §1 · p. 2
- The ordinary game's unrestricted problem was known to be in PSPACE, but whether it was PSPACE-complete remained open after prior NP-hardness results.Prior work also established approximation hardness and NP-completeness under prescribed polynomially bounded time limits.Source: §1 · p. 2
- Related pursuit and graph-searching games use different visibility, movement, capture, or monotonicity rules, so their PSPACE-completeness results do not classify this game.The paper also proves PSPACE-completeness for the directed game with one hunter on oriented graphs of positive minimum outdegree, and for firefighting.Source: §1 · pp. 3–4
- Deciding whether h(G) ≤ k is PSPACE-complete, even for simple bipartite graphs.The number of hunters is part of the input.Source: §1 · p. 4
- Inverse finite-automata intersection nonemptiness reduces to finding a winning strategy by simulating one common word, with inverse transitions supporting an undirected graph.The source problem is PSPACE-complete [21].Source: §1 · p. 4
2. Preliminaries and membership in PSPACE
The preliminaries represent all possible rabbit positions as a territory updated after each shot set. This representation gives a polynomial-space upper bound and frames the inverse-automata problem used for hardness.
2. Preliminaries and membership in PSPACE
- Intermediate graphs may have loops, but hardness graphs have no isolated vertices and resulting digraphs have positive minimum outdegree.Loops permit the rabbit to stay at a vertex; digraph territories use out-neighborhoods.Source: §2 · pp. 4–5
- The territory records every possible surviving position and evolves by removing the first shot set, then taking the neighborhood and removing each subsequent shot set.A strategy is a sequence of shot sets; capture occurs when the territory becomes empty.Source: §2 · pp. 4–5
- A shortest winning sequence has at most 2^n rounds, yielding a nondeterministic polynomial-space search and hence a PSPACE upper bound.The proof discards repeated nonempty territories and stores the current territory, shot set, neighborhood, and round counter in polynomial space.Source: §2 · p. 5
- Inverse finite automata have partial transitions paired with formal inverse symbols, and accept a word only when every transition is defined and its final state is accepting.Their transitions satisfy the inverse relation in (2).Source: §2 · p. 6
- Intersection nonemptiness asks whether one common word takes every automaton to an accepting state; separate accepted words or accepting at different prefixes do not suffice.In the product state space, the task is to reach a tuple in the product of the accepting sets; the product may be exponentially large.Source: §2 · p. 6
- Intersection nonemptiness for inverse finite automata is PSPACE-complete, even over the fixed four-symbol alphabet with one accepting state per automaton [21].The problem remains hard when each accepting set is a singleton.Source: §2 · p. 6
3. PSPACE-completeness
The section develops reductions from common acceptance by inverse finite automata to establish PSPACE-completeness for the Hunters and Rabbit game and firefighting. It describes how guards and a safe clique enforce shared-command simulations, then completes the firefighting reduction and transforms instances to simple graphs in polynomial size.
3.1. Construction
- With k = 9m hunters, guards force complete state tuples to follow one common command, and the test command captures exactly when all component states accept.The construction simulates inverse transitions by traversing transition paths in either direction.Source: §3.1 · pp. 7, 8, 10, 11
3.2. Unrestricted and directed games
- Removing the restriction on initial rabbit positions yields PSPACE-completeness for the unrestricted game through a polynomial-size graph transformation.The construction gives hS(G) ≤ k if and only if h(H) = N + k, where h(H) ≥ N + k.Source: §3.2 · p. 13
- The construction preserves the threshold decision: hS(G) ≤ k iff h(H) = N + k iff h(H) ≤ N + k; BH is simple and bipartite, and both transformations have polynomial size.BH has 4K vertices, where K = N + k ≥ 3. The construction has at most 12n + 68m + 2 vertices, O(n) vertices and O(n²) edges, and is computable in polynomial time.Source: §3.2 · pp. 13–14, §3.1 · p. 13
- Deciding whether h(D) ≤ k is PSPACE-complete for symmetric digraphs with bipartite underlying graphs, and one hunter suffices as a PSPACE-complete decision problem on oriented graphs with positive minimum outdegree.The oriented-graph reduction uses vertex subdivisions and preserves the hunting number according to the cited reduction.Source: §3.2 · p. 14
3.3. Firefighting
- Deciding whether ffn(G) ≤ k is PSPACE-complete for simple undirected graphs.Adding loops represents the firefighting rule that the fugitive may remain at its vertex; the construction uses k = 11m, guard sets of sizes 6m and 9m, and |U| = k + 2.Source: §3.3 · pp. 14–15
- For firefighting, adjusted guards prevent territories from mixing states with transition or test vertices, while loops allow retaining the current class as well as moving to a neighboring class.A good test class has neighborhood size exactly k, enabling capture when all component states accept.Source: §3.3 · pp. 15–16
- A common accepted word yields a winning strategy, while any winning strategy must reach a good test class and thus an accepting tuple.State tuples and good transition classes have neighborhoods of size 12m > k, so capture requires reaching a good test class; following the accepted word uses k hunters each round.Source: §3.3 · p. 16
- The construction of [8, Proposition 4.2] gives h(H) ≤ N + k iff hS(eG) ≤ k, and deleting H’s loops yields a polynomial-size simple graph J with ffn(J) = h(H).Here N = |V(eG)|; both constructions have polynomial size.Source: §3.3 · pp. 16–17