Symmetry as Compression: Kernel Lower Bounds for Pursuit on Tri-Cayley Graphs

Hardness proofs for games like Cops and Robber build the hard instances out of irregular, made-to-order gadgets. In Cops and Robber, a team of pursuers and one visible evader alternate moves along the edges of a graph, and the question is how many pursuers guarantee capture. This raises a natural question: is the game still hard to preprocess when the network is highly symmetric? We study this on tri-Cayley graphs. A tri-Cayley graph has three copies of a group $H$ as its vertices, with every edge pattern repeated by the group's action. It is therefore fully described by $H$ and six small "connection sets" that say which group elements join which copies.

The note's central observation is that symmetry acts as compression. A tri-Cayley graph over a cyclic or abelian group can be written in roughly $d \log |H|$ bits, where $d$ is its degree. That alone rules out the standard tool for proving that no small preprocessing exists. So the real questions for symmetric inputs are different ones. Can the group order be shrunk while preserving the cop number? And for which non-abelian groups does a lower bound become possible again? We propose to prove the barrier, to locate exactly where it breaks, and to back the theory with exact computation on the tri-Cayley families already classified in the literature.

Core Claim

Three background terms are needed. A kernel is a polynomial-time preprocessing step that shrinks an instance to a size bounded by a function of a chosen parameter $k$. Cross-composition is the standard technique for showing that no kernel of polynomial size exists. It packs $t$ instances of an NP-hard problem into one instance whose parameter grows only like $\text{poly}(s) + O(\log t)$, where $s$ is the largest instance size. It was formalized by Bodlaender, Jansen and Kratsch and developed in Clique Cover and Graph Separation: New Incompressibility Results. A tri-Cayley graph $\text{TCay}(H; L_0,L_1,L_2; S_0,S_1,S_2)$ has vertex set three copies of $H$, internal edges given by the sets $L_i$, and edges between copies given by the sets $S_i$.

We make three claims about Cops and Robber on tri-Cayley inputs.

The first is negative but clarifying. The structural parameters used in existing kernelization work give nothing on these graphs. Parameterized Analysis of the Cops and Robber Game and Parameterized Analysis of the Cops and Robber Problem show that Cops and Robber parameterized by vertex cover number $\mathsf{vcn}$ has an exponential kernel but no polynomial compression. On a connected tri-Cayley graph, however, some $S_i$ is non-empty. The edges it induces between two copies form a regular bipartite graph, which has a perfect matching, so $\mathsf{vcn} \ge |H| = n/3$. On this class the parameter is the input size, and the incompressibility result is vacuous. The meaningful parameter is the total connection-set size $d$, together with the number of cops $k$.

The second claim is that there is a compression barrier. Suppose the output of a cross-composition were a tricirculant (a tri-Cayley graph over the cyclic group $\mathbb{Z}_N$) with $d \le \text{poly}(s)+O(\log t)$, and suppose $N \le \text{poly}(ts)$ because the construction runs in polynomial time. Writing the six connection sets as residues gives a description of length

$$ B \;=\; O\big(d \log N\big) \;=\; \big(\text{poly}(s) + O(\log t)\big)\cdot O(\log t + \log s) $$

bits, where $B$ is the bit length of the succinct encoding. Choose $t = s^{C}$ for a large enough constant $C$. Then $B < t$, so we would have an OR-compression of $t$ NP-hard instances into fewer than $t$ bits. This is the regime ruled out by the Bodlaender–Fortnow–Hermelin and Dell–van Melkebeek distillation theorems, unless $\text{NP} \subseteq \text{coNP/poly}$. The precise form of the threshold in those theorems is something we will verify, not assume.

The same argument applies to abelian $H$ given by its invariant factors. It also applies to the non-abelian groups of order $pq$ studied in A Classification of 4-Degree Tri-Cayley Graphs Over a Group of Order 𝑝q, and to any group family with a polynomial-time computable description of polylogarithmic length. For all these classes, cross-composition in the parameter $d$ is impossible. The argument does not depend on Cops and Robber at all. It applies to any game played on such graphs.

The third claim is that the window for lower bounds is computational, not informational. A group of order $n$ is pinned down up to isomorphism by $\text{polylog}(n)$ bits, because there are only $n^{O(\log^2 n)}$ such groups (a classical counting result). Hence every tri-Cayley instance is information-theoretically short. A cross-composition into general tri-Cayley graphs, with $H$ given by its multiplication table, can therefore only exist if it uses groups for which a short description cannot be computed in polynomial time. That ties kernel lower bounds for symmetric pursuit to the difficulty of computing short descriptions of groups. We believe this connection has not been stated before.

Research Program

The first strand turns the barrier into a theorem with exact hypotheses. We will state it for $m$-Cayley graphs in general, with the number of orbits $m$ counted in the parameter. Tri-Cayley graphs remain the main case for two reasons. Their quotient (one vertex per orbit) is a triangle, the smallest quotient containing a genuine cycle. The product of connection labels around $V_0 \to V_1 \to V_2 \to V_0$ is then a new invariant, absent for bi-Cayley graphs, whose quotients have only two vertices. Explicit families with known automorphism groups also already exist. We will check carefully which encodings of $H$ make the description computable in polynomial time. These include cyclic groups, abelian groups given by invariant factors, groups of order $pq$, and groups given by permutation generators. We will also check which variants of the distillation theorem the bound $B < t$ actually triggers.

The second strand asks the positive question the barrier leaves open. Restricted to tricirculants, Cops and Robber has a trivial polynomial compression in $d + \log n$. Is it fixed-parameter tractable, or does it admit a kernel, in $d$ alone? A kernel would have to replace a huge group order $n$ by a small $n'$ with the same cop number.

This needs two ingredients. The first is an upper bound $c \le f(d)$ for tri-Cayley graphs over abelian groups. It would extend the strategy of On the cop number and the weak Meyniel conjecture for algebraic graphs. That paper generalizes Frankl's degree bound for abelian Cayley graphs to Cayley sum graphs and twisted variants, proving $c \le 2|S|$. Its cop strategy assumes a single orbit. We would lift it to three orbits by assigning cops per orbit and per inter-orbit label. Given $f(d)$, only $k < f(d)$ cops matter. Exhaustive game evaluation then runs in $n^{O(f(d))}$ time, which is polynomial for fixed $d$ but not yet fixed-parameter tractable.

The second ingredient is a periodicity conjecture. Fix the connection labels as integers. We conjecture that the cop number of $\text{TCay}(\mathbb{Z}_n; \dots)$ is eventually periodic in $n$, with threshold and period bounded by a function of the labels. This would be the source of a kernel.

The 4-valent families of Ye and Zhang are vertex-transitive but not edge-transitive. Their edges split into those that lie on triangles and those that do not (The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group). These are the first test cases for whether that asymmetry gives the robber a permanent escape loop.

The third strand looks for a lower bound in the open window. The target is non-abelian $H$ given by its multiplication table, chosen from families whose short descriptions are not known to be computable efficiently. We will attempt an OR-cross-composition from Hamiltonian Cycle, following the selection-gadget style of The Parameterized Complexity of Motion Planning for Snake-Like Robots. The difference is that instance selection must be encoded in the group's multiplication, not in local graph regions, because symmetry forbids local gadgets. Either a construction or a precise obstruction would be a result.

Baselines

The naive reference point is to apply the general-graph theory unchanged. That means the vertex-cover-parameterized kernel and incompressibility results of Gahlawat and Zehavi, and the W[2]-hardness in $k$ from On tractability of Cops and Robbers game. On tri-Cayley graphs the first gives nothing, by the $\mathsf{vcn} \ge n/3$ argument above. The second concerns arbitrary graphs and says nothing about this class. Beating this reference means proving any statement whose parameter is sublinear in $n$ on the class.

The strongest existing algorithm is exact backward-induction dynamic programming over joint cop–robber positions. This is the equilibrium oracle used by Equilibrium Policy Generalization and R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability. R2PS reports that this exact computation takes over 2 minutes on graphs with about 1,000 nodes. Our algorithmic contribution is orbit-quotient backward induction. It stores game states only up to the action of $H$, which shrinks the state space by a factor of $|H|$.

We will compare the two on identical graphs, with the same hardware and the same $k$. Both are exact, so correctness is checked by agreement on every instance. Our method beats the baseline if it reaches group orders where plain dynamic programming exhausts memory, with runtime falling roughly by a factor of $|H|$. The ablation that isolates the key ingredient runs the same solver with quotienting switched off.

For the learned-policy check described below, the comparison points are EPG's reported success rates of 1.0 on Grid Maps and 0.98 on Times Square. There is no reported result on Lacuna for any pursuit method, exact or learned, on tri-Cayley graphs.

Why not just…?

Why not just reuse the vertex-cover incompressibility proof of Gahlawat and Zehavi? On these graphs the parameter is already linear in $n$, so the theorem is vacuous. Their gadgets are also irregular and cannot be placed inside a graph whose edges are dictated by a group. This is a proof, not a matter for experiment.

Why not just symmetrize an existing hard instance, for example by taking it as a Cayley graph of some product group? For abelian or succinctly described groups, the barrier shows that any such construction with a small parameter is impossible unless the hierarchy collapses. For general groups, symmetrizing multiplies the group order and typically pushes $d$ beyond $\text{poly}(s)+O(\log t)$. The third strand tests whether a non-abelian construction can avoid this.

Why not just study Cayley graphs, where Biswas and Saha already have strategies? This is a fair alternative. The barrier holds there as well, and we will state it for any number of orbits. The three-orbit case adds the cycle invariant around the triangle quotient and the edge asymmetries of the Ye–Zhang families. We will report whether the cop numbers we compute for tri-Cayley graphs differ in kind from those of comparable Cayley graphs. If they do not, the tri-Cayley emphasis is a matter of presentation and we will say so.

Why not just estimate cop numbers with a learned pursuer such as EPG? A learned policy that wins gives at best an upper bound on the cop number, and one with no certificate. R2PS reports only above-50% success against exploiting evaders on most maps. For the periodicity conjecture we need exact values, so learned policies are an object of evaluation here, not a substitute.

Proposed Experiments

The main computational experiment applies orbit-quotient backward induction to every 4-valent tricirculant with $|H|$ up to roughly 100, using $k \le 3$ cops. This includes the families $\Phi_1, \Phi_2, \Phi_3$ and the classes $X_1, X_2$ from the Ye–Zhang classifications. We will also cover the non-abelian groups of order $pq$, such as orders 21, 39 and 55, and 6-valent tricirculants for a smaller range.

We record the exact cop number as a function of $n$ for each fixed set of integer labels. Two outcomes are decisive. If, for some fixed $d$, the cop number grows without bound as $n$ increases, both the hoped-for bound $c \le f(d)$ and the kernel route fail. The second strand would then reduce to a hardness question. If the values instead settle into periodic patterns with small thresholds, those patterns are the conjectured kernel, and they become targets for proof. For each graph we will also record whether edges on triangles and edges off triangles play different roles in the robber's winning positions.

A secondary experiment uses these exactly solved graphs as a certified test set for zero-shot learned pursuit. It is the reverse of the Dungeon and urban-map corpora used by EPG and R2PS. In vertex-transitive graphs, shortest-path features give no positional cues, which could stress the attention-based features those policies rely on. We will train on the Dungeon corpus following the published protocol, then evaluate on tri-Cayley graphs where the true cop number is known. A large drop from the reported 0.98–1.0 success rates would show that symmetric topologies are a blind spot for these methods. The open-source pursuitFSC2 codebase gives a further multi-agent baseline. On the theory side, the decisive check is the written barrier lemma with exact hypotheses, plus either a cross-composition over non-abelian groups or a proof that every candidate group family in our encodings has a polynomial-time short description.