{"id":"ef503f30-c0ff-45aa-b7ea-7a90eab6b3ae","arxiv_id":"2607.12078","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A digraph admits a completely reachable road coloring iff it is strongly connected, aperiodic, and every vertex subset has at least as many in-neighbors as vertices; the fixed-alphabet version is claimed NP-complete, but the proof has a flaw.","lead":"This paper finds a clean condition for when a directed road network can be colored so any chosen group of agents can be gathered with one color sequence. It also claims the fixed-color version is NP-complete, but that proof contains a gap at a gadget-replacement step.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The NP-hardness reduction's Repl step does not preserve 2-out-regularity: y1 has out-degree 4 and y_{m+1} in-degree 4, so Lemma 4 cannot be applied.","rationale":"I read the manuscript in full. Theorem 1's matching argument is coherent: the Hall condition exactly expresses absorbing subsets, and the construction using letters indexed by nonempty subsets plus Wielandt's bound gives reachability. Theorem 6 also seems to follow from Lemma 5 and [3, Theorem 1]; I did not find a gap there. The problem is squarely in the proof of Theorem 2. The reader's weakest_assumption identifies the same step I would flag: the degree counts after Repl(G1, x1; y1, y_{m+1}, L_m) are inconsistent with the paper's own formal definition. Because G3 inherits G2's degree profile after adding k−2 edges to x, Lemma 4 cannot be invoked, and the claimed polynomial-time reduction from Plesnik's Hamiltonian cycle class is not established. This is load-bearing because the abstract and introduction announce NP-completeness for fixed k as one of the three main results; without this reduction the paper has no support for that result. I am not claiming the theorem is false—a swapped connector order may repair the reduction—but the submitted text's proof is invalid as written. Hence the REJECT verdict is appropriate: major revision is required before the NP-completeness claim can be accepted.","tokens_in":12906,"tokens_out":14840,"duration_ms":131832,"concrete_test":"Recompute the degrees of G2 directly from the Repl definition. Take a small 2-out-regular digraph (e.g., a single vertex with two loops), apply Repl(G, v0; x1, y, F3) to get G1, then apply Repl(G1, x1; y1, y2, L_1) with m=1. Compute deg^+_{G2}(y1) and deg^-_{G2}(y2). If they equal 4 and 4, the proof's claim fails. Then test the swapped connector order, Repl(G1, x1; y_{m+1}, y1, L_m), to see whether it restores 2-out-regularity and the in-degree profile required by Lemma 4; this would indicate whether the flaw is a repairable ordering typo or a deeper issue.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is in Section 3, proof of Theorem 2, in the second replacement step G1 → G2. Under the paper's own Repl definition, replacing vertex x1 of G1 by L_m via Repl(G1, x1; y1, y_{m+1}, L_m) does the following: the two edges of G1 leaving x1 become edges with source y1; the two edges entering x1 become edges with target y_{m+1}; and all edges of L_m remain as they are. Therefore, in G2, deg^+(y1) = 2 (from y1→y2 in L_m) + 2 (the former outgoing edges of x1) = 4, and deg^-(y_{m+1}) = 2 (from y_m→y_{m+1} in L_m) + 2 (the former incoming edges of x1) = 4. The text claims 'G2 retains all properties of G1... it is a 2-out-regular digraph such that deg^-_{G2}(x)=1, deg^-_{G2}(y)=3, deg^-_{G2}(z)=2 for each z∈V_{G2}\\{x,y}'. The actual degrees contradict this: G2 is not 2-out-regular (y1 has out-degree 4 and y_{m+1} has out-degree 0), and the in-degree profile is not that required by Lemma 4. Since G3 is obtained from G2 by adding k−2 edges from every vertex to x, Lemma 4's hypotheses are not met; the claimed equivalence between Hamiltonicity of G and complete reachability of G3 is not established. This is not a cosmetic typo in a lemma; it invalidates the NP-hardness proof of Theorem 2 as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the road-coloring problem for completely reachable automata. It gives a polynomial-time characterization (Theorem 1) of digraphs admitting a completely reachable coloring with an unrestricted number of colors, an NP-completeness result (Theorem 2) for a fixed number k ≥ 2 of colors, and a classification (Theorem 6) of digraphs for which every road coloring is completely reachable. The proofs combine graph-theoretic arguments, Hall's theorem, Wielandt's bound, and results on completely reachable automata from [3].","tokens_in":13337,"tokens_out":14599,"duration_ms":125958,"significance":"The results, if correct, would complete the research program proposed by Bondar and Volkov and would be a substantial contribution to the theory of completely reachable automata. The characterization in Theorem 1 is elegant and algorithmic, and the universal characterization in Theorem 6 is clean. The paper is largely self-contained and builds on prior work in a natural way. However, the NP-hardness proof for fixed k contains a serious technical error that invalidates the reduction as written; this is the main obstacle to publication in current form.","major_comments":[{"comment":"The replacement G1 → G2 via Repl(G1, x1; y1, y_{m+1}, L_m) does not preserve the required degree profile. In G1, vertex x1 has out-degree 2 and in-degree 2. Under Repl, the two outgoing edges of x1 are redirected to y1, and the two incoming edges are redirected to y_{m+1}, while all edges of L_m remain. Hence deg^+(y1)=4, deg^-(y_{m+1})=4, and deg^+(y_{m+1})=0. The text claims G2 is 2-out-regular with deg^-(x)=1, deg^-(y)=3, and all other in-degrees 2; this is false. Moreover, y_{m+1} is a sink, so G2 cannot contain a Hamiltonian cycle at all, contradicting the claimed equivalence. This invalidates the reduction from Plesnik's digraphs and leaves Theorem 2 unproved.","section":"Section 3, proof of Theorem 2, second replacement step"},{"comment":"The displayed equality for the lower bound on the sum of defects is false for k=2. The expression is sum_{v∈V\\{x}} max(0, k - deg^-_G(v)) = (n-2)(k-2) + max(0, k-3), not (n-1)(k-2)-1. For k=2 the paper's formula gives -1, while the correct value is 0. The subsequent contradiction can be repaired because 0 > -(n-3) for n≥5, but the printed equation and the inequality chain need correction.","section":"Section 3, Lemma 4, necessity part"}],"minor_comments":[{"comment":"The notation 'be' appears without the intended subscript in 'be for the link'; it should be 'b_e'.","section":"Section 4, Lemma 5 proof"},{"comment":"Reference [12] contains a typo: 'planar diagraphs' should be 'planar digraphs'.","section":"References"},{"comment":"In the sufficiency proof, the definition of the coloring alpha relies on the simplified digraph being simple. It may be worth explicitly recalling that the passage from G to its simplification preserves complete reachability (as stated in Section 1.4), to avoid any perception of a gap.","section":"Section 2, proof of Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's main characterization theorems (Theorems 1 and 6) appear sound and are appealing. The NP-hardness proof, however, has a concrete and easily verified flaw in the construction of G2; the resulting digraph is not 2-out-regular and has a sink, so the claimed equivalence with Hamiltonicity fails. This is a load-bearing error for Theorem 2. I do not recommend rejection because the error seems localized to the gadget construction and may be repairable with a carefully designed prime-size expansion gadget, but it requires nontrivial reworking of Section 3. The authors should also correct the k=2 case in Lemma 4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the bottom line: Theorem 1 is a real result and the proof holds together; Theorem 6 is plausible and probably correct. The NP-completeness proof for Theorem 2, however, has a hole that is not cosmetic.\n\nTheorem 1 gives a clean characterization — strong connectivity, aperiodicity, and the absorbing-set condition — and the sufficiency construction using Hall's theorem and Wielandt's bound is elegant. The complexity analysis is correct. That alone is a valuable contribution.\n\nThe trouble is Section 3. In the step from G1 to G2, the paper replaces x1 by the double-line L_m. Under their own definition of Repl, the two outgoing edges of x1 become edges out of y1, and the two incoming edges become edges into y_{m+1}. L_m already gives y1 two outgoing edges and y_{m+1} two incoming edges. So y1 has out-degree 4, y_{m+1} has in-degree 4, and y_{m+1} has out-degree 0. The paper's claim that G2 is 2-out-regular with in-degrees 1, 3, and 2 is simply wrong. Lemma 4 cannot be applied to G3, and the claimed equivalence with Hamiltonicity is not established. The reduction may be repairable, but as written the NP-completeness result is unproven.\n\nTheorem 6 is short and rests on the external [3, Theorem 1]; I did not find a gap there. The self-citation is not a problem — it is the natural prior work. Lemma 5 also looks fine.\n\nThis paper deserves a serious referee, mostly to check Theorem 1 and Theorem 6, and to push the authors to fix or drop the fixed-k claim. I would not rely on the NP-hardness result in its present form, but the characterization results are worth engaging with. For anyone in automata theory or road coloring, Theorems 1 and 6 are useful and citable once the paper is cleaned up.","headline":"Theorem 1 is a solid, genuinely new characterization; the fixed-k NP-completeness proof in Theorem 2 has a real hole that the authors need to repair before the claim can be trusted.","tokens_in":13816,"tokens_out":4692,"would_cite":true,"duration_ms":43508,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","05C20","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A digraph admits a completely reachable coloring exactly when it is strongly connected, aperiodic, and every subset of vertices is absorbing.","keywords":["completely reachable automata","road coloring","digraph coloring","absorbing subset","aperiodic digraph","NP-completeness","synchronizing automata","W(S,n) digraphs"],"falsifier":"Find a finite strongly connected aperiodic digraph in which every subset of vertices has at least as many in-neighbors as its size, yet no edge labeling makes every nonempty subset reachable; such a digraph would contradict Theorem 1.","tokens_in":12757,"feed_emoji":"🎨","tokens_out":5859,"duration_ms":51641,"temperature":0.7,"pith_summary":"This paper completes the road-coloring program for completely reachable automata. It proves a full characterization: a finite digraph admits a coloring that makes every nonempty subset of vertices reachable precisely when the digraph is strongly connected, aperiodic, and every subset of vertices has at least as many in-neighbors as its size. The paper shows these conditions can be checked in polynomial time, that fixing the number of colors turns the decision problem NP-complete, and that the digraphs for which every coloring is completely reachable are exactly the W(S,n) family with S generating the cyclic group. The results settle the open questions this line of work set out to answer.","feed_headline":"Three graph conditions decide road-colorability","feed_subtitle":"A polynomial-time characterization, an NP-complete fixed-color variant, and a full classification of universal cases.","key_machinery":"The main mechanism is the bipartite representation BP(G), which converts the absorbing condition (every subset has at least as many in-neighbors as its own size) into Hall's condition for a matching that covers the source side. Such a matching is then used to define a road coloring whose letters are the nonempty subsets of the vertex set: each letter U acts by sending the in-neighborhood of U onto U. A second mechanism is the defect of a letter (the number of states lost when applying it), which links completely reachable colorings with a fixed number k of colors to the existence of cycles with special in-degree structure, and from there to Hamiltonian cycles.","core_discovery":"On the paper's own terms, the central discovery is a three-way classification. First, completely reachable colorings exist exactly for digraphs that are strongly connected, aperiodic, and absorbing for every subset; the proof constructs such a coloring from a matching in the bipartite representation, using every nonempty vertex subset as a letter. Second, for every fixed k≥2, recognizing whether a k-color completely reachable coloring exists is NP-complete, proved by a reduction from Hamiltonian cycle on a restricted class of digraphs. Third, all colorings are completely reachable exactly for digraphs whose simplification is isomorphic to a member of the family W(S,n) whose generator set S a","pith_inferences":["The fixed-color NP-completeness suggests that the number of colors interacts with the underlying digraph's cycle structure in a way that might also appear in other road-coloring variants, such as synchronizing colorings.","The absorbing condition is a kind of expansion condition; one could test whether an analogous condition characterizes other families of automata defined by reachability of subsets.","The exponential number of colors in the unrestricted construction raises the practical question of whether a polynomial number of colors always suffices when the three conditions hold.","The universal classification might be extended by asking which digraphs have all colorings synchronizing—a question the paper notes is still open."],"forward_implications":["Completely reachable road colorings are now fully understood at the level of underlying digraphs: existence is decidable in polynomial time by checking three graph properties.","The universal characterization gives a linear-time algorithm to decide whether every coloring of a given digraph is completely reachable.","The NP-completeness result shows that minimizing the number of labels is intrinsically hard even when an unrestricted coloring is easy to construct.","The proof of the unrestricted case yields an explicit coloring with 2^{|V|}-1 letters, giving a concrete upper bound on labels needed.","The three results together close the research program that motivated the study of completely reachable automata."],"fun_headline_variants":["Polynomial, NP-complete, or universal: road coloring classified","Road coloring: complete reachability split three ways","Three-way verdict for completely reachable road coloring","Road coloring reachability: easy, hard, and always works"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The NP-hardness reduction relies on the assumption that replacing a chosen vertex with the funnel and double-line gadgets yields a 2-out-regular digraph whose in-degrees are exactly 1, 3, and 2 (one vertex each), which is what the argument needs to invoke its main lemma.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial, NP-complete, or universal: road coloring classified","Road coloring: complete reachability split three ways","Three-way verdict for completely reachable road coloring","Road coloring reachability: easy, hard, and always works"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000671,"raw_usage":{"total_tokens":2807,"prompt_tokens":567,"completion_tokens":2240,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":311,"completion_tokens_details":{"reasoning_tokens":2174}},"tokens_in":311,"tokens_out":2240,"duration_ms":18353,"temperature":1.0,"reasoning_tokens":2174,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T06:43:26.634862+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a finite strongly connected aperiodic digraph in which every subset of vertices has at least as many in-neighbors as its size, yet no edge labeling makes every nonempty subset reachable; such a digraph would contradict Theorem 1.","supporting_citations":[],"review_version":2}