A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity

Jakob T. Spooner; Thomas Erlebach

REVIEW 3 major objections 5 minor 19 references

A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that on edge-periodic graphs—where each edge follows a repeating availability pattern—one can decide in $O(\mathrm{LCM}(L)\cdot n^3)$ time whether the cop or robber wins, and compute a winning strategy in the same bound.

desk verdict Sound decision procedure for EPCR via reachability games; the cycle robber-win upper bound has an unproved strip-crossing claim that needs a real proof. read the letter →

arxiv 1908.06828 v1 pith:QYPOVT4N submitted 2019-08-19 cs.DS cs.DM

Thomas Erlebach , Jakob T. Spooner This is my paper · ORCID

classification cs.DScs.DM MSC 05C5768R1068Q25

keywords edge-periodicgraphscopsandrobbersreachabilitygamestemporalpursuit-evasionattractorsetschedulednetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

On an edge-periodic graph—a graph whose edges switch on and off according to repeating bit patterns—this paper studies the classic question of whether one cop can eventually catch one robber. The main result is that the infinite game can be compressed into a finite directed game graph, because the whole edge schedule repeats after $\mathrm{LCM}(L)$ steps. Deciding which player wins becomes an attractor computation on that finite graph, running in $O(\mathrm{LCM}(L) \cdot n^3)$ time, and the same computation returns an explicit winning strategy. The paper also proves a threshold for cycles: any edge-periodic cycle with at least $2 \cdot l \cdot \mathrm{LCM}(L)$ vertices is robber-win, with $l=1$ when $\mathrm{LCM}(L) \geq 2 \cdot \max L$ and $l=2$ otherwise, and it gives cop-win cycles of lengths $1.5 \cdot \mathrm{LCM}(L)$ and $3 \cdot \mathrm{LCM}(L)$ in those two cases. A reader should care because edge-periodic graphs model networks whose links are available only at scheduled times, and this supplies a decision procedure for the basic pursuit-evasion question on such arenas.

What carries the argument

The load-bearing construction is a transformation $\beta(G^\tau)$ that maps an edge-periodic graph to a finite directed game graph whose states are $(c,r,s,t)$ with $t \in [\mathrm{LCM}(L)]$, whose edges alternate between cop-owned and robber-owned states, and whose final states are the capture positions $c=r$. The argument then runs on the attractor set $\mathrm{Attr}(F)$, the least fixed point collecting all states from which the cop can force the token into a capture state; it is computed by the standard reachability-game fixpoint, where cop states with at least one edge into the attractor and robber states with all edges into the attractor are added in rounds. This attractor is what decides the winner and, through memoryless strategies, yields the actual winning play.

What would settle it

Take an edge-periodic cycle with $n = 2 \cdot l \cdot \mathrm{LCM}(L) - 1$ and simulate the cop's attractor strategy against the robber's proposed Hide/Escape strategy for every phase of the edge schedule; if the cop ever captures the robber, the claimed robber-win threshold is false. A more direct check is to compute $\mathrm{Attr}(F)$ by the paper's own construction on that cycle and see whether any cop start vertex $v$ has $(v,r,C,0) \in \mathrm{Attr}(F)$ for all robber starts $r$.

Watch

Extended reading notes

Core claim

The paper's central claim is that the infinite-time game on an edge-periodic graph can be reduced, without loss, to a finite reachability game. Since every edge pattern length divides $\mathrm{LCM}(L)$, the relevant information in any game position—cop vertex, robber vertex, whose turn, and the time step modulo the global period—fits into $O(\mathrm{LCM}(L) \cdot n^2)$ states. The cop wins exactly when some start vertex has all $n$ corresponding initial states inside the attractor of the capture states, and computing that attractor takes $O(\mathrm{LCM}(L) \cdot n^3)$ time; the same computation also produces a memoryless winning strategy for whichever player wins. For edge-periodic cycles, the paper further claims that length at least $2 \cdot l \cdot \mathrm{LCM}(L)$ forces a robber win, with $l=1$ when $\mathrm{LCM}(L) \geq 2 \cdot \max L$ and $l=2$ otherwise, and it exhibits cop-win cycles of length $3 \cdot \mathrm{LCM}(L)$ and $1.5 \cdot \mathrm{LCM}(L)$ showing that thresholds of this size are needed.

Load-bearing premise

The robber-win threshold for cycles rests on an unproven-in-detail claim that on an infinitely long periodic path the robber can always keep moving right and stay ahead of the cop, and the proof applies that claim to a finite cycle by unrolling it into an infinite path without a full phase-by-phase argument; if that unrolling fails for some schedule phase, the cycle threshold does not follow.

Editorial extensions

If this is right

If Theorem 2 is correct, deciding the winner is polynomial whenever $\mathrm{LCM}(L)$ is bounded by a polynomial in $n$, and cubic in $n$ when all edge pattern lengths are constant.
If Theorem 11 is correct, the winning player receives an explicit memoryless strategy in the same $O(\mathrm{LCM}(L) \cdot n^3)$ time, so the decision procedure is constructive.
For edge-periodic cycles, the threshold $2 \cdot l \cdot \mathrm{LCM}(L)$ means any cycle at least that long is guaranteed to let the robber evade forever, regardless of the schedule's phases.
The cop-win cycle constructions show that the robber-win guarantee cannot start below $1.5 \cdot \mathrm{LCM}(L)$ in the $l=1$ case or below $3 \cdot \mathrm{LCM}(L)$ in the $l=2$ case.
The paper's $k$-cop generalization gives $O(\mathrm{LCM}(L) \cdot k \cdot n^{k+2})$ time, so the framework extends beyond one cop at the price of an extra factor $k \cdot n^k$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An immediate extension the paper does not pursue is that any temporal graph whose entire edge schedule has a global period $T$ should admit the same reduction with $O(T \cdot n^3)$ states, giving a decision procedure for a broader class of scheduled arenas.
The paper leaves open the complexity when $\mathrm{LCM}(L)$ is exponential; the exponential game graph makes NP-hardness a plausible conjecture, but nothing in the paper establishes it.
The gap between the upper bound $2 \cdot l \cdot \mathrm{LCM}(L)$ and the cop-win constructions suggests a natural test: in the $l=2$ case, determine whether a robber-win cycle of length $2.5 \cdot \mathrm{LCM}(L)$ exists, which would tighten the threshold.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the central algorithmic result, Theorem 2, is sound and useful; the paper's second half on cycles has a real gap in the proof of the robber-win upper bound.

The genuinely new thing here is the reduction from edge-periodic cops and robbers to reachability games, with the finite state space indexed by time modulo LCM(L). That reduction is clean, the state space size and out-degree count are right, and the O(LCM(L)·n³) bound follows from the standard linear-time attractor algorithm. The strategy-synthesis extension (Theorem 11) is also a straightforward but nice consequence. I checked the transformation conditions and the proof of Lemma 8; both hold. This is the first decision procedure of this kind for temporal graphs, and it is a solid contribution.

The cycle part is where I have concerns. Lemma 12 (infinite path) asserts the robber's clearance time inequality T^L_R(i) ≤ t + (i−1)B − 1, and the proof just states it. The strips S_i are defined by C's first traversal times; R may arrive at an edge just after its active slot and wait up to l_e − 1 steps. No bound is given on accumulated waiting over S_2 ∪ … ∪ S_i. If those waits accumulate, C could enter S_i before R has cleared it, and the one-strip lead collapses. Unrolling the cycle to an infinite path in Theorem 13 does not repair this; the same inequality is the bottleneck. The Hide/Escape mode distinction also deserves a more formal treatment: the Escape strategy invokes Lemma 12 after only a one-step shift, and it's not obvious the antipodal distance plus the cycle length gives the required margin in all schedule phases. So the 2·l·LCM upper bound looks plausible but is not rigorously supported as written.

Minor thing: reference [3] and [11] share the same arXiv identifier, which looks like a typo; worth correcting.

Overall, the decision procedure is a keeper, and the cycle gap is probably fixable, but it needs a real proof rewrite before publication. Send it to a serious referee.

Referee Report

3 major / 5 minor

Summary. This paper defines the edge-periodic Cops and Robbers (EPCR) game on edge-periodic graphs, in which each edge has a periodic availability pattern of length l_e. The main algorithmic result (Theorem 2) is an O(LCM(L)\cdot n^3) algorithm that decides whether a single cop can catch a robber, based on a reduction to a reachability game on a state space of size O(LCM(L)\cdot n^2). Theorem 11 extends this to computing winning strategies. In Section 4, the paper studies edge-periodic cycles: Theorem 13 claims an upper bound of 2\cdot l\cdot LCM(L) on the length needed to guarantee robber-win, and Theorems 14\textendash 15 provide lower-bound constructions. The reachability-game reduction is well motivated, and the complexity analysis is straightforward.

Significance. If the missing proofs are supplied, the paper makes a solid contribution: it appears to be the first to apply reachability-game techniques to cops-and-robbers in a temporal setting, and it gives a clean polynomial-time decision procedure when LCM(L) is polynomial in n. The cycle results are also interesting, giving upper and lower bounds that are within a constant factor. The lower-bound constructions in Theorems 14\textendash 15 are explicit and credible. However, the current version has two significant proof gaps, one in the central equivalence (Lemma 7) and one in the cycle upper bound (Lemma 12 and Theorem 13).

major comments (3)

[Section 3.2, Lemma 7] Lemma 7 asserts the equivalence between EPCR positions and attractor states in the reachability game \beta(G^\tau), but it is stated without proof. Since Theorem 2, Lemma 8, and Theorem 11 all rely on this equivalence, the proof should be supplied. A direct induction on the number of moves, matching each EPCR position with the corresponding state in the reachability game and each legal C/R move with the edges of E', would be appropriate.
[Section 4, Lemma 12] The proof of Lemma 12 uses the inequality T_R^L(i) \le t + (i-1)B - 1 to assert that R clears strip S_i before C can enter it. This inequality is not established: the strips S_i are defined by C's first traversal times, whereas R may arrive at an edge just after its active time slot and then wait up to l_e - 1 steps. Accumulated waiting over the edges of S_2 \cup \cdots \cup S_i could erase the one-strip lead, allowing C to enter S_i before R has cleared it. The proof needs an explicit worst-case bound on R's waiting, or a different invariant that controls the robber's per-strip progress.
[Section 4, Theorem 13] The Escape-mode argument applies Lemma 12 by viewing the cycle as an infinite path and unrolling it, but it does not verify that the hypotheses of Lemma 12 hold at the start of an Escape period: R is not in general positioned at the first vertex of a strip S_2, C's monotone movement 'to the right' is not defined on a cycle without a fixed orientation, and the proof does not show that the robber can preserve the required distance until the next Hide period. The conclusion that R survives until the Hide period ends is therefore not rigorously supported by the text as written.

minor comments (5)

[References] Reference [3] and reference [11] both cite the identifier 'arXiv:1407.1647'; one of these is likely a misprint and should be corrected.
[Abstract and Introduction] The phrase 'O(LCM(L)\cdot n^3) upper bound on the time required to decide' describes the algorithm's running time, not an upper bound on the game duration; this wording should be adjusted.
[Theorem 15] The statement that the edge with pattern 01 'has been selected so that it is present whenever C's strategy crosses that edge' is asserted without a timing verification; a short case analysis or timing table would make the construction easier to check.
[Lemma 12] The lemma's statement says 'if LCM = max L' and 'at least LCM otherwise', but the proof uses the equivalent cases B = 2\cdot LCM and B = LCM; the relationship between the statement and proof should be clarified.
[End of Section 3] The k-cop generalization is stated without proof; a brief argument for the claimed O(LCM(L)\cdot k \cdot n^{k+2}) bound would be helpful, though this is not a central result.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the reachability-game reduction is self-contained, and the cycle upper bound's gap is a proof gap, not a circular reduction.

full rationale

I walked the derivation chain. Theorem 2 builds a finite reachability game whose states are all 4-tuples (c, r, s, t) with t ranging over LCM(L), whose edges implement exactly the legal alternating cop/robber moves, and whose final states are exactly the positions with c = r. The cop-win condition is then derived directly from the rule that the robber chooses its start vertex after seeing the cop's choice. No parameter is fitted, no target conclusion is assumed as an input, and the complexity bound follows from |V'| = O(LCM(L) * n^2) and out-degree at most n. The lower-bound constructions in Theorems 14 and 15 are explicit examples with concrete winning strategies for the cop, so they are independent of the upper-bound claims. The only concern I found is that Lemma 12 asserts T_L_R(i) <= t + (i-1)B - 1 without fully deriving a bound on accumulated waiting times, so the cycle robber-win upper bound in Theorem 13 may rest on an unproved claim; this is a correctness gap, not a circular reduction. Citations to Berwanger and to Grädel et al. are standard external results and are not authored by the present authors, and no self-citation is load-bearing. Hence the paper is not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central proof relies on three standard results from the reachability-game literature, all external to this paper. No free parameters are introduced: the LCM and pattern lengths are inputs, and the lower-bound constructions use explicit patterns. No invented entities appear.

assumptions (4)

domain assumption Reachability games are determined and the attractor set is the winning region (Berwanger [3]).
Used in Lemma 7 and Theorem 6 to transfer winning conditions from the reachability game to the original game.
domain assumption Attractor computation takes O(|V|+|E|) time (Grädel et al. [9]).
Used to establish the O(LCM(L)·n^3) running time of Theorem 2.
domain assumption Memoryless winning strategies exist for reachability games (Berwanger [3]).
Used in Theorem 11 to extract strategies for the EPCR game.
domain assumption Edge-periodic graphs require each edge to be present at least once per period (Definition 1).
This is part of the model, inherited from [7]; it ensures no edge becomes permanently unavailable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity." pith.science (2026). https://pith.science/paper/QYPOVT4N

@misc{pith2026190806828,
  author       = {Pith},
  title        = {Pith review of: A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QYPOVT4N}},
  note         = {Machine review of arXiv:1908.06828}
}

abstract

This paper considers a game in which a single cop and a single robber take turns moving along the edges of a given graph $G$. If there exists a strategy for the cop which enables it to be positioned at the same vertex as the robber eventually, then $G$ is called cop-win, and robber-win otherwise. We study this classical combinatorial game in a novel context, broadening the class of potential game arenas to include the edge-periodic graphs. These are graphs with an infinite lifetime comprised of discrete time steps such that each edge $e$ is assigned a bit pattern of length $l_e$, with a 1 in the $i$-th position of the pattern indicating the presence of edge $e$ in the $i$-th step of each consecutive block of $l_e$ steps. Utilising the already-developed framework of reachability games, we extend existing techniques to obtain, amongst other results, an $O(\textsf{LCM}(L)\cdot n^3)$ upper bound on the time required to decide if a given $n$-vertex edge-periodic graph $G^\tau$ is cop or robber win as well as compute a strategy for the winning player (here, $L$ is the set of all edge pattern lengths $l_e$, and $\textsf{LCM}(L)$ denotes the least common multiple of the set $L$). Separately, turning our attention to edge-periodic cycle graphs, we give proof of a $2\cdot l \cdot \textsf{LCM}(L)$ upper bound on the length required by any edge-periodic cycle to ensure that it is robber win, where $l = 1$ if $\textsf{LCM}(L) \geq 2\cdot \max L $, and $l=2$ otherwise. Furthermore, we provide lower bound constructions in the form of cop-win edge-periodic cycles: one with length $1.5 \cdot \textsf{LCM}(L)$ in the $l=1$ case and one with length $3\cdot \textsf{LCM}(L)$ in the $l=2$ case.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[11]

Cops and Robbers, Game Theory and Zermelo's Early Results

A. Kehagias and G. Konstantinidis. Cops and robbers, game the ory and Zer- melo’s early results. arXiv:1407.1647, 2014

work page Pith review arXiv 2014
[1]

Aigner and M

M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1 – 12, 1984

work page 1984
[2]

Berarducci and B

A. Berarducci and B. Intrigila. On the cop number of a graph. Advances in Applied Mathematics , 14(4):389 – 403, 1993

work page 1993
[4]

Bonato and G

A. Bonato and G. MacGillivray. A general framework for discrete -time pursuit games. Unpublished manuscript , 2015

work page 2015
[5]

Bonato and R

A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs , volume 61 of Student Mathematical Library . American Mathematical Society, 2011

work page 2011
[6]

Casteigts

A. Casteigts. A Journey Through Dynamic Networks (with Excursions) . Habil- itation ` a diriger des recherches, University of Bordeaux, June 20 18

work page
[7]

Casteigts, P

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. T ime-varying graphs and dynamic networks. In H. Frey, X. Li, and S. Ruehrup, e ditors, Pro- ceedings of the 10th International Conference on Ad-hoc, Mo bile, and Wireless Networks (ADHOC-NOW 2011) , volume 6811 of LNCS, pages 346–359. Springer Berlin Heidelberg, 2011

work page 2011
[8]

T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-ev asion in mobile robotics. Autonomous Robots, 31(4):299–316, 2011

work page 2011

Show all 19 references

[9]

Gr¨ adel, W

E. Gr¨ adel, W. Thomas, and T. Wilke, editors. Automata Logics, and Inﬁnite Games: A Guide to Current Research . Springer-Verlag New York, Inc., New York, NY, USA, 2002

2002
[10]

Hahn and G

G. Hahn and G. MacGillivray. A note on k-cop, l-robber games on g raphs. Discrete Mathematics , 306(19):2492–2497, 2006. Creation and Recreation: A Tribute to the Memory of Claude Berge

2006
[12]

Kehagias, D

A. Kehagias, D. Mitsche, and P. Pralat. The role of visibility in purs uit/evasion games. Robotics, 4:371–399, 2014

2014
[13]

O. Michail. An introduction to temporal graphs: An algorithmic pe rspective. Internet Mathematics , 12(4):239–280, 2016

2016
[14]

Spirakis

Othon Michail and Paul G. Spirakis. Elements of the theory of dy namic net- works. Communications of the ACM , 61(2):72–72, January 2018

2018
[15]

Nowakowski and P

R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a g raph. Discrete Mathematics, 43(2):235–239, 1983. 15

1983
[16]

T. D. Parsons. Pursuit-evasion in a graph. In Y. Alavi and D. R. Lick, editors, Theory and Applications of Graphs , pages 426–441. Springer Berlin Heidelberg, 1978

1978
[17]

Patsko, S

V. Patsko, S. Kumkov, and V. Turova. Pursuit-evasion games . In T. Basar and G. Zaccour, editors, Handbook of Dynamic Game Theory , pages 1–87. Springer International Publishing, 2017

2017
[18]

Quilliot

A. Quilliot. Jeux et pointes ﬁxes sur les graphes . PhD thesis, University of Paris VI, 1978

1978
[19]

B. A. Rankin. Ramanujan: Twelve lectures on subjects sugges ted by his life and work. The Mathematical Gazette , 45(352):166, 1961

1961
[20]

Seymour and R

P.D. Seymour and R. Thomas. Graph searching and a min-max the orem for tree-width. Journal of Combinatorial Theory, Series B , 58(1):22–33, 1993. 16

1993

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [11]

Cops and Robbers, Game Theory and Zermelo's Early Results

A. Kehagias and G. Konstantinidis. Cops and robbers, game the ory and Zer- melo’s early results. arXiv:1407.1647, 2014

work page Pith review arXiv 2014

[2] [1]

Aigner and M

M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1 – 12, 1984

work page 1984

[3] [2]

Berarducci and B

A. Berarducci and B. Intrigila. On the cop number of a graph. Advances in Applied Mathematics , 14(4):389 – 403, 1993

work page 1993

[4] [4]

Bonato and G

A. Bonato and G. MacGillivray. A general framework for discrete -time pursuit games. Unpublished manuscript , 2015

work page 2015

[5] [5]

Bonato and R

A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs , volume 61 of Student Mathematical Library . American Mathematical Society, 2011

work page 2011

[6] [6]

Casteigts

A. Casteigts. A Journey Through Dynamic Networks (with Excursions) . Habil- itation ` a diriger des recherches, University of Bordeaux, June 20 18

work page

[7] [7]

Casteigts, P

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. T ime-varying graphs and dynamic networks. In H. Frey, X. Li, and S. Ruehrup, e ditors, Pro- ceedings of the 10th International Conference on Ad-hoc, Mo bile, and Wireless Networks (ADHOC-NOW 2011) , volume 6811 of LNCS, pages 346–359. Springer Berlin Heidelberg, 2011

work page 2011

[8] [8]

T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-ev asion in mobile robotics. Autonomous Robots, 31(4):299–316, 2011

work page 2011