{"id":"11d41275-a43a-4465-89df-b01d96eadfa2","arxiv_id":"2507.09283","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The m-eternal domination problem and its Roman and Italian variants are NP-hard on narrow graph classes, and four infinite regular grids admit strongly optimal eternally-dominating guard sets.","lead":"This paper proves that several \"eternal domination\" games, in which guards must continually defend a graph against repeated attacks, are NP-hard even on restricted graph classes. It also constructs optimal guard configurations for four infinite regular grids, showing that in these grids the eternal domination number equals the ordinary domination number.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6's hexagonal-grid defense is not a translation: the two parity classes move by different vectors, so the proof never establishes that the post-attack configuration is dominating; the strategy cannot be iterated as written.","rationale":"The reader's weakest_assumption is correctly placed. The NP-hardness proofs also contain compressed steps, such as the forced configuration in Theorem 1 and the \"guard in B\" assumption in Theorem 3, but those gaps are plausibly repairable by forcing an additional attack, for example attacking an unguarded P or B vertex. Theorem 6 is different: the stated mechanism is not merely underjustified; it is literally false, and it is the only mechanism offered for the hexagonal grid. My own residue check of one post-attack configuration suggests that S' may still be a perfect code, so I would not reject the paper or the theorem, but the proof as written is not sound at that step. This does not change the reader's CONDITIONAL verdict: accept the program, require a corrected invariant or explicit verification for Theorem 6, and repair the smaller gaps in the NP-hardness proofs.","tokens_in":13823,"tokens_out":27581,"duration_ms":330713,"concrete_test":"Simulate the move rules of Theorem 6 on T3 restricted to coordinates modulo 8 (or to a large finite patch), starting from S as defined. For each attack direction (up, down, right from an even guard, plus the symmetric odd cases), form S' by applying the paper's two parity-class translations and check that every vertex has domination index exactly 1 with respect to S', i.e., |N[v]∩S'|=1, and that S' is reachable by legal one-step guard moves. If all checks pass, the hexagonal construction is sound but the proof needs a new invariant; if any check fails, the proposed strategy fails on the first guard turn and Theorem 6 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in Theorem 6. For an attack on v=(i*,j*+1) with s=(i*,j*) even, the specified rule moves S⊢ by (0,1) and S⊣ by (0,-1). The proof then says \"the new position of the guards is a translation of S by one unit in the same direction.\" This is false: the two classes do not receive the same vector, and in fact no single integer translation maps S to the resulting set. Writing S = L ∪ (L-(1,0)), the result is (L+(0,1)) ∪ (L-(1,1)); a translation would require (0,2)∈L, but L, generated by (2,2) and (3,-1), does not contain (0,2). Therefore the induction for the m-eternal strategy is missing: later attacks occur on a configuration that is not a translate of S, and the paper gives no invariant showing that these configurations remain (strongly optimal) dominating sets. The specific post-attack set may in fact be a perfect code, and the other three grid proofs, based on genuine translations, are on firmer ground, but as written Theorem 6's m-eternal claim is unproved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the m-eternal domination game and two weighted variants (Roman and Italian) in the m-eternal setting. The authors give polynomial-time reductions from Dominating Set and Italian Domination to show NP-hardness of m-Eternal Domination on bipartite graphs of diameter four (Theorem 1), m-Eternal Roman Domination on split graphs (Theorem 2), and m-Eternal Italian Domination on split graphs (Theorem 3). For infinite square, octagonal, hexagonal, and triangular grids, they exhibit strongly optimal dominating sets (perfect codes) and attempt to show that these sets are also m-eternal via translation or piecewise-movement strategies (Theorems 4-7). The paper introduces the notion of strong optimality for infinite graphs and proves that every strongly optimal dominating set is optimal (Lemma 1).","tokens_in":14024,"tokens_out":21532,"duration_ms":252139,"significance":"The results would be useful additions if the proofs are completed: the three NP-hardness theorems target natural restricted graph classes, and the grid constructions connect perfect codes with m-eternal domination in a clean way. Lemma 1 is correct, and the square, octagonal, and triangular grid constructions (Theorems 4, 5, and 7) are concise and appear sound because they use genuine translations. The reduction ideas in Theorems 1-3 are standard and plausible. However, several central proofs have load-bearing gaps: the reverse direction of Theorem 1 is not established, the forward direction of Theorem 3 applies Lemma 4 to an object that may not satisfy its hypotheses, the reverse direction of Theorem 3 assumes an unjustified initial configuration, and the hexagonal-grid defense in Theorem 6 does not produce the claimed translate and has no iterability argument. Because these gaps affect the main claims of the paper, substantial revision is needed.","major_comments":[{"comment":"The reduction's reverse direction depends on reaching a configuration in which P and w each have exactly one guard, and the proof claims that such a configuration can be obtained after attacking an unguarded vertex of P. This is not demonstrated and is false as stated: an attack on a vertex p in P must be answered by a guard moving from w to p, since w is the only neighbor of p, so the guard is removed from w; if P already contained guards, the result need not have exactly one guard on P. The case where every vertex of P is already guarded is also not addressed. Since the construction of the dominating set S of G requires the bound k on the number of guards outside P union {w}, this gap is load-bearing for the equivalence of the instances.","section":"Section 3, Theorem 1 (reverse direction)"},{"comment":"The forward direction invokes Lemma 4 with tf = k, but no Italian dominating function on H of weight k with connected support is actually defined. The natural choice f'(u_i) = f(v_i) and f' = 0 on B is not always Italian on H: a B-vertex w_i^{(j)} may see only one neighbor with value 1 (for example, if f(v_i) = 1 and v_i has no positive neighbor), giving neighbor-sum 1; and if the support of f has size 1, A-vertices outside the support also have neighbor-sum 1. Thus the claimed upper bound gamma_infty_I(H) <= k + 1 is not established by the argument given.","section":"Section 3, Theorem 3 (forward direction)"},{"comment":"The reverse direction assumes 'an initial configuration of k+1 guards such that B contains at least one guard.' This assumption is not justified: a winning strategy with k+1 guards might begin with all guards on A, since the Italian condition on B-vertices can be satisfied entirely from A. The proof needs to show that such an initial configuration can be chosen without loss of generality, or it must handle configurations with no guard in B.","section":"Section 3, Theorem 3 (reverse direction)"},{"comment":"The prescribed piecewise guard movements do not produce a translate of S. In the first listed case, with s = (i*, j*) in S_even and attacked vertex v = (i*, j*+1), the rule sends even-parity guards by (0,1) and odd-parity guards by (0,-1). Writing S = L union (L-(1,0)) with L generated by (2,2) and (3,-1), the resulting set is (L+(0,1)) union (L-(1,1)), which is not a translate of S; no single translation can map both cosets correctly because L does not contain (0,2). The sentence 'The new position of the guards is a translation of S by one unit in the same direction' is therefore false. Moreover, the paper gives no invariant showing that the resulting configuration is dominating or that the strategy can be iterated for subsequent attacks, since the next attack occurs on a configuration not known to have the form of S. This leaves the m-eternal claim for the hexagonal grid unproved.","section":"Section 4, Theorem 6"}],"minor_comments":[{"comment":"The notation for the two parity classes is inconsistent: the text uses the same symbol (or near-identical symbols) for both S-sub-* and S-sub-* sets. Use S_0 and S_1, or another clearly distinguishable pair, throughout the proof.","section":"Section 4, Theorem 6"},{"comment":"The sentence 'and that the considered configuration is not part of a winning strategy, a contradiction' is grammatically incomplete and should be rewritten; the missing logical dependency makes the reverse direction even harder to follow.","section":"Section 3, Theorem 1"},{"comment":"There is a typo in 'm-Eternal Italiam Domination'; also, the definition of B in the construction is missing a closing brace and should be written as B = { w_i^{(j)} : 1 <= i <= n and 1 <= j <= n+2 }.","section":"Section 3, Theorem 3"},{"comment":"The definition of 'at least as good' via existence of an injective map is nonstandard and could be clarified by stating explicitly that it is a cardinality comparison; as written it is easy to confuse with a map between vertex sets of the graph.","section":"Section 2.3"},{"comment":"Several grammatical slips should be corrected, for example 'the guards moves as follows', 'for every ... the guard on ... move to', and 'contains n+2 copies of V' instead of 'contain n+2 copies'. These do not affect the mathematics but should be fixed in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on 2507.09283. The paper splits into two halves. The infinite-grid work is uneven: square, octagonal, and triangular grids are done cleanly, while the hexagonal grid case is broken as written. The complexity half has plausible hardness results, but two of the three reductions have gaps a referee will not overlook.\n\nCredit where it's due. The 'strongly optimal' perfect-code framework is fine; Lemma 1 is a standard injectivity argument and it's correct. For T4, T8, and T6 the sets are genuine perfect codes and the defense is an honest translation of the entire guard set by the attack vector, so the invariant survives a single attack and all later attacks. Those three theorems look correct. Lemmas 2-4 (floating-guard upper bounds, connected versions included) are also correct. The citation pattern is appropriate—the relevant split-graph and finite-grid prior work is acknowledged.\n\nWhere it breaks. Theorem 6, the hexagonal grid, has a real flaw, and the stress-test note is right. The response to an upward attack sends S⊢ up by (0,1) and S⊣ down by (0,-1). Writing S = L ∪ (L-(1,0)), the new set is (L+(0,1)) ∪ (L-(1,1)), which is not a translate of S: any translation would require (0,2) ∈ L, and the lattice generated by (2,2) and (3,-1) does not contain (0,2). So the assertion 'the new position is a translation' is false, the post-attack configuration is never shown to be dominating, and the strategy cannot be iterated. The right-attack case has the same defect. The result may be salvageable—spot checks show the post-attack set locally looks like a perfect code—but the paper supplies neither the verification nor an invariant, so Theorem 6 is unproved as written.\n\nThe complexity proofs need work too. Theorem 1's reverse direction asserts, in one sentence, that a configuration with exactly one guard on P and one on w can be forced by attacking a P vertex. That needs an argument: a defender could keep guards off P and dominate P through w, and the attack dynamics have to force the guard on w to move. Probably repairable. Theorem 3's forward direction is more serious: the natural copy of an Italian function of G on A, with zeros on B, need not be an Italian dominating function of H—if f(vi)=1 and all G-neighbors are zero, the corresponding B-vertex has neighbor-sum 1. There is also a parameter mismatch (the instance is stated with k+1, the forward proof uses weight k), and the reverse direction assumes a guard in B without justification. Theorem 2's pigeonhole argument, by contrast, is essentially fine.\n\nBottom line: researchers working on domination games get real value from the three grid theorems and the reduction ideas, but as submitted this needs major revision. I'd send it to a referee—the hex case and the Italian reduction merit careful scrutiny—but I would not cite it in its current form.","headline":"Three of the four grid theorems are solid; the hexagonal-grid proof is genuinely broken, and the Italian-domination reduction has gaps a referee will not overlook.","tokens_in":14587,"tokens_out":30616,"would_cite":false,"duration_ms":342304,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C57","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"m-Eternal domination is NP-hard on bipartite diameter-four and split graphs; on four infinite regular grids, eternal domination needs no more guards than ordinary domination.","keywords":["m-eternal domination","eternal domination game","Roman domination","Italian domination","NP-hardness","split graphs","bipartite graphs","infinite grids"],"falsifier":"On the hexagonal grid, apply the exact movement prescribed in Theorem 6 to an attack and inspect every vertex's closed neighborhood; finding a single vertex whose closed neighborhood contains two guards after the move would falsify the assertion that the set remains a strongly optimal dominating set. On the finite side, a polynomial-time algorithm for m-eternal domination on bipartite graphs of diameter four, or for the Roman or Italian variants on split graphs, would contradict the NP-hardness theorems unless P=NP.","tokens_in":1872,"feed_emoji":"🛡️","tokens_out":5229,"duration_ms":117458,"temperature":0.7,"pith_summary":"The paper studies the m-eternal domination game, where a defender places guards on a graph and must keep the guarded vertices a dominating set while repelling an infinite sequence of attacks; each turn the attacker names a vertex and the defender moves any number of guards one edge, with one guard landing on the attacked vertex. On finite graphs, the paper proves that the decision problems for m-eternal domination, m-eternal Roman domination, and m-eternal Italian domination, together with their connected variants, are NP-hard even on very restricted graph classes: bipartite graphs of diameter four for the first, and split graphs for the Roman and Italian versions. On four infinite regular grids—square, octagonal, hexagonal, and triangular—the paper constructs a single dominating set that is strongly optimal and also an m-eternal dominating set, so these grids can be defended forever with exactly as many guards as ordinary domination requires. The interest is that eternal defense can be achieved at no extra cost in guarding density on these natural infinite graphs, while the finite problem remains computationally hard in narrow classes.","feed_headline":"Minimal guard sets defend four infinite grids forever","feed_subtitle":"Square, octagonal, hexagonal, and triangular grids match static domination with eternal guard counts; NP-hardness sharpens the finite…","key_machinery":"The carrying mechanism for the hardness results is a two-step template: first, show that if a graph has a connected dominating set $Z$, then an extra floating guard turns a static dominating configuration into an eternal one (for Roman domination, two guards on each vertex of $Z$ plus one floating guard; for Italian domination, the support of an Italian dominating function plus one floating guard). Then reduce from Dominating Set by building an auxiliary graph—bipartite for Theorem 1, split for Theorems 2 and 3—where the extra construction forces a winning guard configuration to encode a dominating set of the original graph. For the grids, the central object is a strongly optimal dominating set, a set $S$ such that every vertex's closed neighborhood intersects $S$ in exactly one vertex; the closed neighborhoods of $S$ partition the grid. The guard response is a combinatorial translation (or, for the hexagonal grid, a parity-split movement) that carries $S$ to another translate of itself or to a set that is claimed to be another strongly optimal dominating set, preserving the partition property.","core_discovery":"For the infinite grids, the central discovery is that there exist vertex subsets $S$ whose closed neighborhoods partition the vertex set—the paper calls such sets strongly optimal dominating sets—and that the same $S$ is an m-eternal dominating set. For the square, octagonal, hexagonal, and triangular grids, the guard-movement strategy is: when a vertex not in $S$ is attacked, every guard moves along the same pattern (a translation for the square, octagonal, and triangular grids; a two-part movement splitting the two parity classes for the hexagonal grid), and the resulting configuration is again a strongly optimal dominating set. Consequently $\\gamma_\\infty(T_4)=\\gamma(T_4)$, $\\gamma_\\infty(T_8)=\\gamma(T_8)$, $\\gamma_\\infty(T_3)=\\gamma(T_3)$, and $\\gamma_\\infty(T_6)=\\gamma(T_6)$ in the strong-optimality sense. In finite graphs, the paper establishes NP-hardness: m-Eternal Domination is NP-hard on bipartite graphs of diameter four via a reduction from Dominating Set, and m-Eternal Roman Domination and m-Eternal Italian Domination are NP-hard on split graphs via related reductions that also cover the connected variants.","pith_inferences":["A testable extension is to verify coordinate by coordinate that the parity-split response on the hexagonal grid preserves the strong-optimality partition; if it does, the same strategy pattern gives a template for other periodic grids with two-color vertex partitions.","The reductions are likely transferable to any graph class where Dominating Set or Italian Domination is hard and where the auxiliary graph can be built; the bipartite-diameter-four and split classes are chosen because they make the encoding clean, not because the technique is specific to them.","The strongly optimal sets for the four grids are all periodic patterns, so one could compute the exact m-eternal domination density for every finite rectangular region cut from these grids and compare with the known $O(n+m)$ gaps for finite square grids."],"forward_implications":["If the reductions are correct, the m-eternal domination number, m-eternal Roman domination number, and m-eternal Italian domination number cannot be computed in polynomial time unless P=NP, even when inputs are restricted to bipartite graphs of diameter four (for m-eternal domination) or to split graphs (for the Roman and Italian variants).","On each of the four infinite grids, ordinary domination number and m-eternal domination number coincide in the strong-optimality sense, so no extra guards are needed for eternal defense compared with static domination.","The connected variants are as hard as the non-connected ones on the same graph classes, because the constructed configurations remain connected throughout the winning strategies.","The strongly optimal dominating sets provide a uniform upper bound on guard density for square, octagonal, hexagonal, and triangular grids, and by the injection-based optimality lemma these sets are at least as good as any other dominating set."],"supporting_citations":[{"why":"Supplies the base NP-hardness of Dominating Set that the reductions of Theorems 1 and 2 start from.","marker":"[14]"},{"why":"Shows Domination is NP-hard on bipartite graphs of diameter three, the closest prior result that the diameter-four construction of Theorem 1 extends.","marker":"[23]"},{"why":"Establishes that Roman Domination is NP-hard on split graphs, the class used in the split-graph reduction of Theorem 2.","marker":"[9]"},{"why":"Establishes that Italian Domination is NP-hard on split graphs, the starting problem for the reduction of Theorem 3.","marker":"[8]"},{"why":"Provides the analogous m-eternal vertex-cover argument that the floating-guard Lemmas 2 and 3 mirror.","marker":"[20]"},{"why":"Defines the m-eternal domination game and the m-eternal domination number used throughout the paper.","marker":"[15]"},{"why":"Gives the domination-number lower bound for finite square grids that motivates the infinite-grid optimality questions.","marker":"[17]"},{"why":"Provides the best-known upper bound for finite square grids, the comparison point for the infinite-grid results.","marker":"[21]"}],"fun_headline_variants":["Eternal guard numbers match domination on four infinite grids","m-Eternal Domination is NP-hard on bipartite and split graphs","Four infinite grids achieve eternal domination with minimal guards","NP-hardness results for eternal domination variants"],"cache_read_input_tokens":16768,"weakest_assumption_plain":"The load-bearing premise is the assertion in the hexagonal-grid proof that after the parity-split guard movement the guards still occupy a strongly optimal dominating set, a claim the proof states without a coordinate-by-coordinate check.","fun_headline_variants_meta":{"raw":{"variants":["Eternal guard numbers match domination on four infinite grids","m-Eternal Domination is NP-hard on bipartite and split graphs","Four infinite grids achieve eternal domination with minimal guards","NP-hardness results for eternal domination variants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1397,"prompt_tokens":1006,"completion_tokens":391,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":327}},"tokens_in":622,"tokens_out":391,"duration_ms":5040,"temperature":1.0,"reasoning_tokens":327,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:01:42.977236+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the hexagonal grid, apply the exact movement prescribed in Theorem 6 to an attack and inspect every vertex's closed neighborhood; finding a single vertex whose closed neighborhood contains two guards after the move would falsify the assertion that the set remains a strongly optimal dominating set. On the finite side, a polynomial-time algorithm for m-eternal domination on bipartite graphs of diameter four, or for the Roman or Italian variants on split graphs, would contradict the NP-hardness theorems unless P=NP.","supporting_citations":[{"cited_title":"Acta Informatica61, 357–382 (2024)","cited_arxiv_id":null,"evidence_quote":"Shows Domination is NP-hard on bipartite graphs of diameter three, the closest prior result that the diameter-four construction of Theorem 1 extends."},{"cited_title":"Discrete mathematics278(1-3), 11–22 (2004).https://doi.org/ 10.1016/J.DISC.2003.06.004","cited_arxiv_id":null,"evidence_quote":"Establishes that Roman Domination is NP-hard on split graphs, the class used in the split-graph reduction of Theorem 2."},{"cited_title":"A Note on Roman \\{2\\}-domination problem in graphs","cited_arxiv_id":"1804.09338","evidence_quote":"Establishes that Italian Domination is NP-hard on split graphs, the starting problem for the reduction of Theorem 3."},{"cited_title":"Australasian Journal of Combinatorics45, 235–250 (2009) 18 T","cited_arxiv_id":null,"evidence_quote":"Provides the analogous m-eternal vertex-cover argument that the floating-guard Lemmas 2 and 3 mirror."},{"cited_title":"Journal of Combinatorial Mathematics and Combinatorial Computing 52(01) (2005)","cited_arxiv_id":null,"evidence_quote":"Defines the m-eternal domination game and the m-eternal domination number used throughout the paper."},{"cited_title":"SIAM Journal on Discrete Mathematics25(3), 1443–1453 (2011)","cited_arxiv_id":null,"evidence_quote":"Gives the domination-number lower bound for finite square grids that motivates the infinite-grid optimality questions."},{"cited_title":"Theoretical ComputerScience 794,27–46(2019)","cited_arxiv_id":null,"evidence_quote":"Provides the best-known upper bound for finite square grids, the comparison point for the infinite-grid results."}],"review_version":1}