{"id":"e473eea2-5ece-4252-8bef-1da14af482ff","arxiv_id":"1908.06828","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"On edge-periodic graphs, deciding the winner in one-cop-one-robber play takes O(LCM(L) n^3) time, and cycles of length at least 2 l LCM(L) are always robber-win.","lead":"Cops-and-robbers on graphs is extended to graphs whose edges appear and disappear on repeating schedules, and the paper gives an algorithm to decide the winner. The result opens a door to pursuit-evasion analysis on temporal networks, such as transit or duty-cycled sensor systems.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 is sound, but the cycle robber-win bound rests on an unproved strip-crossing rate in Lemma 12.","rationale":"The reader's conditional verdict is appropriate. The central claim highlighted in the strongest_claim, Theorem 2, survives scrutiny: the reduction to a reachability game is faithful, and the complexity bound follows directly from the state count and per-state out-degree. The weaker point is Theorem 13, which depends on Lemma 12. The reader identified the unrolling of the cycle to an infinite path as the weak assumption; my read agrees with that location but sharpens it: the real gap is inside Lemma 12's strip argument, specifically the unproved inequality T^L_R(i) ≤ t + (i−1)B − 1. This inequality implicitly assumes the robber can clear each strip at the same rate as the cop's first-traversal schedule, without accounting for waiting periods caused by edge absence. Since each edge can be absent for up to l_e − 1 consecutive steps, waits could in principle accumulate across the edges of several strips. If that happens, the robber may lose the one-strip lead and the proof of the cycle upper bound collapses. This is a proof gap rather than a demonstrated counterexample, so the appropriate verdict remains conditional. The concrete test proposed is an exhaustive small-instance search, which would settle whether the claimed thresholds actually hold and whether the concern lands as a theorem failure or only as an omission in the proof.","tokens_in":14594,"tokens_out":34331,"duration_ms":388231,"concrete_test":"Enumerate all edge-pattern assignments for a small period set, e.g. L = {2, 3} or {2, 4}, on cycles of length exactly n = 2·l·LCM(L), and also on infinite path prefixes with robber starting at the Lemma 12 threshold distance. For each instance, compute the cop-winning region with the paper's own reachability-game construction over time modulo LCM(L). A single cop-winning state at distance at least the lemma threshold, or a cop-winning cycle of length n = 2·l·LCM(L), would refute Lemma 12 / Theorem 13. If none is found, the theorem likely survives, but the proof must still supply a rigorous derivation of the clearance-time inequality T^L_R(i) ≤ t + (i−1)B − 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main decision procedure (Theorem 2) is internally sound: the finite attractor construction over modulo-LCM states correctly represents the alternating cop/robber turns, and the O(LCM(L) · n^3) bound follows from |V'| = O(LCM(L) · n^2) with out-degree at most n per state. I found no flaw in this central algorithmic claim. The load-bearing weakness is in the cycle result. Theorem 13's Escape mode invokes Lemma 12, whose proof asserts the inequality T^L_R(i) ≤ t + (i−1)B − 1 for the robber's clearance time of strip S_i. That inequality is not established: strips are defined by C's first traversal times, whereas R may arrive at an edge just after its active slot and wait up to l_e − 1 steps. The proof gives no bound on accumulated waiting over the edges of S_2 ∪ ... ∪ S_i. If 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 does not repair this, because the same strip inequality is the bottleneck. Thus the 2·l·LCM upper bound is plausible but not rigorously supported as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14767,"tokens_out":7794,"duration_ms":76707,"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":[{"comment":"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":"Section 3.2, Lemma 7"},{"comment":"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":"Section 4, Lemma 12"},{"comment":"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.","section":"Section 4, Theorem 13"}],"minor_comments":[{"comment":"Reference [3] and reference [11] both cite the identifier 'arXiv:1407.1647'; one of these is likely a misprint and should be corrected.","section":"References"},{"comment":"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.","section":"Abstract and Introduction"},{"comment":"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.","section":"Theorem 15"},{"comment":"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.","section":"Lemma 12"},{"comment":"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.","section":"End of Section 3"}],"recommendation":"major_revision","confidential_remarks":"The missing proof of Lemma 7 is straightforward to supply, but the gap in Lemma 12 and its use in Theorem 13 is more serious and requires genuine new work. I would be willing to review a revised version. The paper is within the scope of a discrete-algorithms journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nMinor thing: reference [3] and [11] share the same arXiv identifier, which looks like a typo; worth correcting.\n\nOverall, 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.","headline":"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.","tokens_in":15323,"tokens_out":1557,"would_cite":true,"duration_ms":16649,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C57","68R10","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["edge-periodic graphs","cops and robbers","reachability games","temporal graphs","pursuit-evasion games","attractor set","scheduled networks"],"falsifier":"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$.","tokens_in":14363,"feed_emoji":"👮","tokens_out":11928,"duration_ms":103715,"temperature":0.7,"pith_summary":"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.","feed_headline":"Periodic edge graphs: cops-and-robbers winner is computable fast","feed_subtitle":"A reachability-game reduction decides the winner in O(LCM(L)·n³) time and even returns a winning strategy.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Defines the classical one-cop one-robber game whose rule set EPCR adopts.","marker":"[15]"},{"why":"Independently defines the same game and the cop-win property that edge-periodic graphs generalize.","marker":"[18]"},{"why":"Supplies the attractor-set fixpoint and memoryless winning-strategy theorems used in the proof.","marker":"[3]"},{"why":"Provides the reachability-game framework and the polynomial-time attractor algorithm that gives the time bound.","marker":"[9]"},{"why":"Introduces the edge-periodic graph model that forms the arena of the game.","marker":"[7]"},{"why":"Notes the connection between cops-and-robbers and reachability games that motivates the reduction.","marker":"[11]"}],"fun_headline_variants":["Edge-periodic graphs: cops-and-robbers decided in O(LCM(L)·n³)","Cops-and-robbers on periodic edges: O(LCM·n³) winner check","Reachability game solves cops-and-robbers on edge-periodic graphs","Edge-periodic cycles: long enough guarantees robber win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Edge-periodic graphs: cops-and-robbers decided in O(LCM(L)·n³)","Cops-and-robbers on periodic edges: O(LCM·n³) winner check","Reachability game solves cops-and-robbers on edge-periodic graphs","Edge-periodic cycles: long enough guarantees robber win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002085,"raw_usage":{"total_tokens":8238,"prompt_tokens":1210,"completion_tokens":7028,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":826,"completion_tokens_details":{"reasoning_tokens":6942}},"tokens_in":826,"tokens_out":7028,"duration_ms":57512,"temperature":1.0,"reasoning_tokens":6942,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:33:45.927606+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"Nowakowski and P","cited_arxiv_id":null,"evidence_quote":"Defines the classical one-cop one-robber game whose rule set EPCR adopts."},{"cited_title":"Quilliot","cited_arxiv_id":null,"evidence_quote":"Independently defines the same game and the cop-win property that edge-periodic graphs generalize."},{"cited_title":"Gr¨ adel, W","cited_arxiv_id":null,"evidence_quote":"Provides the reachability-game framework and the polynomial-time attractor algorithm that gives the time bound."},{"cited_title":"Casteigts, P","cited_arxiv_id":null,"evidence_quote":"Introduces the edge-periodic graph model that forms the arena of the game."},{"cited_title":"Cops and Robbers, Game Theory and Zermelo's Early Results","cited_arxiv_id":"1407.1647","evidence_quote":"Notes the connection between cops-and-robbers and reachability games that motivates the reduction."}],"review_version":1}