Parity Sweeps: Bounding Non-Monotone Rabbit Hunting by Graph Bandwidth

Consider a game played on a network. A hunter fires at a few nodes each round, and an invisible rabbit must hop to a neighbouring node after every shot. The question is how many shots per round guarantee a kill. The known theory explains this game only when the hunter is forbidden to let the rabbit back into territory already cleared. Under that "monotone" rule, the shots needed track pathwidth, a measure of how thin a graph is when laid out along a line. Real winning strategies often break the rule. They let the rabbit slip back into cleared ground and catch it on a later pass, and on some trees this cuts the requirement from arbitrarily many shots to two. Nobody has a layout-based quantity that predicts what these rule-breaking strategies can achieve. Nobody has a practical way to build them on large graphs either. This note proposes one. Lay the graph out along a line with small bandwidth, meaning every edge joins two nodes that sit close together in the ordering. Then slide a window along that line. The window's job is not to guard a boundary but to exploit the rabbit's forced alternation between the two halves of a bipartite graph. Each pass shoots only the half the rabbit must currently occupy, and a second pass handles the other parity.

The payoff has two parts. On the theory side, this gives an upper bound on the non-monotone hunting number $h(G)$ in terms of a layout quantity that can sit near half of what any monotone strategy pays. The clearest test case is grids, where Hunting a rabbit: complexity, approximability and some characterizations leaves $h$ undetermined. On the practical side, mature bandwidth heuristics become generators of explicit hunting strategies. Each strategy can be checked in polynomial time by tracking the set of places the rabbit could be. That would give the first scalable, certified upper bounds on $h(G)$ for graphs with hundreds or thousands of vertices. The hunting literature currently offers only hardness results and exponential-kernel algorithms.

Core Claim

Let $G$ be bipartite with a vertex ordering $\pi$ of bandwidth $b$, and colour classes $A$ and $B$. A rabbit that starts in $A$ is in $A$ at even rounds and in $B$ at odd rounds. Define the parity load of $\pi$ as

$$\lambda(\pi) = \max_{i,\; X \in \{A,B\}} \left|\{v \in X : i \le \pi(v) \le i+b\}\right|,$$

the largest number of same-coloured vertices in any $b+1$ consecutive positions. Write $\lambda(G)$ for its minimum over orderings, the parity bandwidth.

The target theorem is $h(G) \le \lambda(G)$. The strategy has two passes. In each round the window advances by one position, and the hunter shoots only the window vertices of the colour the tracked rabbit must occupy. A rabbit ahead of the window cannot jump behind it, because every edge spans at most $b$ positions. A rabbit inside the window of the correct parity is shot. The second pass repeats this with the parity flipped. The exact window width and the order in which the hunter shoots and the rabbit moves still need to be pinned down in the proof; that is the first deliverable.

For non-bipartite $G$, the same strategy runs on the bipartite double cover $G \times K_2$. Hunting a rabbit is hard uses this same construction for its NP-hardness reduction. A shot at $(v,c)$ in the double cover projects to a shot at $v$ in $G$.

Since $\lambda(\pi)$ is roughly $\lceil (b+1)/2 \rceil$ on balanced layouts, and monotone hunting costs at least pathwidth (Further results on the Hunters and Rabbit game through monotonicity proves $pw(G) \le mh(G) \le pw(G)+1$), the bound predicts a factor-of-about-two separation between monotone and non-monotone hunting. That separation should appear exactly on graphs whose pathwidth is close to their bandwidth. Grids are the canonical case. Their bandwidth and pathwidth both scale with the side length $n$, and Lions and contamination: Monotone clearings shows that monotone clearing in its related lions game needs $n$ agents. The parity sweep would use roughly $n/2$.

The claim is deliberately limited. Bandwidth is at least pathwidth, so the parity sweep cannot explain the unbounded tree gap of Recontamination Helps a Lot to Hunt a Rabbit, where $h(T)=2$ while $mh(T)$ grows without bound. Those trees have large bandwidth too. The proposal treats this as the boundary of the method rather than hiding it. It also tests a natural extension in which the window may rewind, moving back over cleared positions and so allowing recontamination. The question is how much of the tree gap that extension recovers.

Relation to Prior Work

Three papers motivate the question. Further results on the Hunters and Rabbit game through monotonicity ties monotone hunting to pathwidth, a cut-based layout parameter, but says nothing about non-monotone strategies. Recontamination Helps a Lot to Hunt a Rabbit shows the monotone bound can be arbitrarily loose. Hunting a rabbit: complexity, approximability and some characterizations proves $h(G)$ is NP-hard even on bipartite graphs, hard to approximate additively within $O(n^{1-\epsilon})$, and open on grids. That hardness constrains the proposal. It does not promise approximation of $h$. It offers certified upper bounds that are tight on structured families, with tightness checked by exact computation on small instances. The same paper's $l$-factor approximation for round-limited hunting, obtained via minimum vertex cuts on a layered graph, is a different object: it bounds strategies by horizon length, not by layout.

The method comes from the bandwidth literature. The node-centroid heuristic of A New Node Centroid Algorithm for Bandwidth Minimization alternates two moves: shifting each vertex toward the average position of its neighbours, and local hill-climbing swaps. It is the ordering engine. Its objective is modified here to minimise parity load instead of bandwidth. Cuthill-McKee ordering, as used in Improving Graph Generation by Restricting Graph Bandwidth, supplies a cheap alternative ordering. The exact algorithms of Exact and approximate bandwidth and Even Faster Exact Bandwidth supply true optimal bandwidth on small graphs, so that the effects of the heuristic and of the sweep can be separated. None of these works treats an ordering as a pursuit schedule.

The nearest structural analogue is the forward-only cut-set state graph in Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms. The rewinding window extension is its non-monotone counterpart. The "monotonic path" layout work in Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search shares vocabulary only. Its monotonicity is about distance to a query decreasing along a search path, not about recontamination, and it is not a competitor.

Research Program

The theoretical part has three pieces.

The first is to prove $h(G) \le \lambda(G)$ with the correct window width and shoot-then-move convention. The proof should also characterise when the sweep is monotone in the sense of Further results on the Hunters and Rabbit game through monotonicity. The expectation is that it is not: during pass one, rabbits of the untracked parity roam freely, so the set of possible rabbit locations grows. That would make it a genuine witness of the value of recontamination.

The second is to derive closed-form parity loads for grids, tori, and caterpillars. Lower bounds on $h$ for these families would then be pursued, to see whether the sweep is tight. Wherever the file reports a monotone lower bound, the sweep's cost would be set against it.

The third is to define rewinding sweeps. Here the window's position is any walk over the ordering rather than a forward march. The questions are which tree families from Recontamination Helps a Lot to Hunt a Rabbit admit constant-cost rewinding sweeps, and whether the resulting "rewind number" sits strictly between $h$ and $\lambda$.

The computational part has two pieces. The first is an exact solver for $h(G)$ on graphs up to roughly 20 vertices. It works by backward reachability over subsets of possible rabbit locations, using the parsimonious-shot pruning described for these games. The second is a sweep generator plus verifier that scales to sparse graphs with thousands of vertices. Verification propagates the possible-location set round by round at a cost proportional to rounds times edges, so every reported upper bound is a certificate, not an estimate.

Baselines

The naive reference point is the monotone window sweep along the same ordering. It shoots every vertex in the window regardless of colour, and so costs about $b+1$ hunters. Any parity sweep that does not beat it by close to a factor of two on balanced bipartite graphs has failed.

The strongest existing upper bound is the monotone strategy implied by pathwidth, $mh(G) \le pw(G)+1$ from Further results on the Hunters and Rabbit game through monotonicity. On small graphs it will be computed exactly; on large ones, from the vertex-separation number of the best ordering found by an equal-budget local search. That search gets the same ordering heuristics, the same wall-clock limit, and the same number of restarts as the parity-load search.

The ordering engines are compared on matched budgets. On the 80-instance Harwell-Boeing set, A New Node Centroid Algorithm for Bandwidth Minimization reports 0.00% deviation from best-known bandwidth for NCHC, 8.27% for the fast variant FNCHC, and 59.59% for Gibbs-Poole-Stockmeyer. These numbers anchor how good the input orderings are. For hunting numbers themselves there is no reported result found on Lacuna for any benchmark, since every hunting paper in the file is purely theoretical. The hunting comparisons therefore rest on the exact solver for small graphs and on certified bounds for large ones.

Two further baselines complete the picture. One is a belief-greedy hunter that, each round, shoots the $k$ vertices whose removal most shrinks the possible-location set. The other is a parity-halved vertex-separation sweep, which isolates whether the bandwidth window or the parity trick is doing the work. Beating the competitors means a smaller certified hunter count than both pathwidth+1 and greedy on a majority of instances, together with exact agreement with the solver on grids and caterpillars wherever the solver can reach.

Why not just…?

Why not just halve a pathwidth sweep by parity instead of using bandwidth? This is the most serious threat. A pathwidth ordering may have a smaller boundary than any bandwidth window. The risk is that a vertex on the boundary that is skipped because of its colour lets an untracked rabbit step back into cleared ground, because edges in a pathwidth ordering can be long. The bandwidth bound on edge length is exactly what blocks this in the proof sketch. The parity-halved separation sweep is run as an ablation and checked with the same verifier. If it is valid and cheaper on most instances, the proposal's central quantity becomes parity vertex separation and the claim is restated around it.

Why not just run a greedy belief-state hunter? Greedy shooting is easy and adaptive. But Hunting a rabbit is hard gives additive inapproximability, so no local rule is safe in general. Greedy also gives no structural explanation of why it succeeds or fails. It is included as a baseline. If it matches the parity sweeps on grids, the theoretical bound still stands, but the practical contribution shrinks to the certificates.

Why not just solve the game exactly? The exact solver is part of the program, but its state space is all subsets of vertices, roughly $2^n$. It stops near 20 vertices, far below the Harwell-Boeing sizes. It serves to measure tightness, not to replace the sweeps.

Proposed Experiments

The first experiment checks tightness on small graphs. All connected bipartite graphs up to about 12 vertices, together with grids, tori, caterpillars, and the recontamination trees, up to about 20 vertices, are solved exactly. Then $h$, $pw+1$, $\lambda$ computed from optimal bandwidth orderings found with the exact algorithms, and the rewind number are compared. The decisive check is whether $\lambda$ equals $h$ on grids, and whether the cost ratio between monotone and parity strategies approaches two as grid size grows.

The second experiment concerns scale. On the Harwell-Boeing instances, parity sweeps are generated from Cuthill-McKee, FNCHC, and parity-load-tuned NCHC orderings. For non-bipartite matrices the double-cover construction is used. Each strategy is verified, and certified hunter counts and runtime are reported against pathwidth+1 and greedy. The synthetic families of Learning-Based Algorithms for Graph Searching Problems (Erdős–Rényi graphs, random trees, lobsters, circular ladders) are used as a second, structurally varied suite.

The third experiment maps where the method breaks. On the tree families with $h(T)=2$, the test is how many hunters forward sweeps and rewinding sweeps need. A finding that rewinding sweeps stay bounded while $\lambda$ grows would be the clearest evidence that recontamination corresponds to a backtracking layout. A finding that they also grow would locate the tree gap outside any layout explanation of this kind.