Completely Reachable Road Coloring

Mikhail V. Volkov; Yinfeng Zhu

REVIEW 2 major objections 3 minor 16 references

A digraph admits a completely reachable coloring exactly when it is strongly connected, aperiodic, and every subset of vertices is absorbing.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 06:43 UTC pith:LSHXJV7W

load-bearing objection 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. the 2 major comments →

arxiv 2607.12078 v3 pith:LSHXJV7W submitted 2026-07-13 cs.FL cs.CC

Completely Reachable Road Coloring

Mikhail V. Volkov , Yinfeng Zhu This is my paper

classification cs.FL cs.CC MSC 68Q4505C2068Q25

keywords completely reachable automataroad coloringdigraph coloringabsorbing subsetaperiodic digraphNP-completenesssynchronizing automataW(S,n) digraphs

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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.

Core claim

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

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

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.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

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.

read the 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.

Theorem 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.

The 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.

Theorem 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.

This 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.

Referee Report

2 major / 3 minor

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].

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 (2)

[Section 3, proof of Theorem 2, second replacement step] 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 3, Lemma 4, necessity part] 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.

minor comments (3)

[Section 4, Lemma 5 proof] The notation 'be' appears without the intended subscript in 'be for the link'; it should be 'b_e'.
[References] Reference [12] contains a typo: 'planar diagraphs' should be 'planar digraphs'.
[Section 2, proof of Theorem 1] 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.

Circularity Check

0 steps flagged

No significant circularity: Theorem 1 is proved from Hall+Wielandt, and the self-cited Bondar–Volkov theorem is external independent support.

full rationale

The paper is a parameter-free combinatorial classification. Theorem 1 is derived from first principles: necessity uses properties of reachable subsets; sufficiency constructs a road coloring over P'(V) using Hall's theorem to define matchings f_U and Wielandt's theorem to show iterating in-neighbor sets covers all vertices. No quantity in the theorem is defined in terms of the DFA's image sets, and no fitted parameter is renamed as a prediction. The NP-hardness proof (Theorem 2) is built on Plesnik's independent Hamiltonian cycle reduction plus lemmas proved in the text; the only self-citation, [3, Theorem 1], is invoked as a general automata criterion (cyclic letter plus a letter of defect 1 implies complete reachability for prime states), which is a prior published result whose assumptions do not include the digraph characterization being proved, so it is genuine evidence rather than a circular restatement. Theorem 6's sufficiency also cites [3, Theorem 1]; although this is a self-citation by the first author, the cited theorem is external and independently proved, and the new contribution is the classification by W(S,n), not a repackaging of that theorem. The reviewer-flagged Repl degree-count issue is a correctness concern in the reduction, not a case of a result being equivalent to its inputs by construction. Therefore no circular step is present.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

The paper is parameter-free; no fitted constants or new physical entities are introduced. Its results depend on standard theorems (Hall, Wielandt, Bertrand, Hopcroft-Karp) and three external automata/algorithmic results ([3], [9], [12]). The only ad hoc load-bearing premise is the replacement-gadget degree preservation, which fails by direct calculation.

axioms (7)

standard math Hall's marriage theorem: a matching covering V' exists iff every U⊆V' has |N(U)|≥|U|
Used in Theorem 1 to equate absorbency of all vertex subsets with existence of a matching covering the source part of the bipartite representation.
standard math Wielandt's theorem: every strongly connected aperiodic n-vertex digraph has a path of length (n−1)^2+1 between every pair of vertices
Used in the sufficiency proof of Theorem 1 to show that iterating the in-neighbor operation k times reaches all vertices.
domain assumption [3, Theorem 1]: a prime-state DFA with a cyclic-permutation letter and a defect-1 letter is completely reachable
External theorem by Bondar and the first author; used in Lemma 4 and Theorem 6, cited but not re-proved in this paper.
domain assumption Hoffmann [9, Proposition 3]: if an n-state DFA has m<n defect-1 letters and every (n−1)-element subset is reachable, the group generated by defect-0 letters has at most m orbits
Black-box group-theoretic result used in Lemma 4 necessity to force the defect-0 letter to be a cyclic permutation; its exact statement is not reproduced.
domain assumption Plesnik's polynomial-time reduction from SAT to Hamiltonian cycle in digraphs with in/out-degree 1 or 2 [12]
Basis of the NP-hardness reduction in Theorem 2; cited, not derived.
ad hoc to paper The digraph G2 obtained by Repl(G1, x1, y1, ym+1, L_m) is 2-out-regular and satisfies the degree profile required by Lemma 4
Asserted in the proof of Theorem 2. Under the paper's own Repl definition, y1 inherits x1's outgoing edges in addition to L_m's two edges, and y_{m+1} inherits x1's incoming edges in addition to L_m's two edges, so the asserted degree profile is false.
standard math Bertrand's postulate: the least prime greater than n is at most 2n
Used to justify choosing m in polynomial time so that |V_G1|+m is prime.

pith-pipeline@v1.3.0-alltime-deepseek · 12497 in / 29421 out tokens · 277248 ms · 2026-08-02T06:43:26.634862+00:00 · methodology

0 comments

read the original abstract

We determine which digraphs admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. Such digraphs are recognizable in polynomial time; however, the problem becomes NP-complete when the size of the label alphabet is fixed. We also classify the digraphs for which every edge labeling results in a completely reachable automaton.

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 7 canonical work pages

[1]

Israel J

Adler, R.L., Goodwyn, L.W., Weiss, B.: Equivalence of topological Markov shifts. Israel J. Math.27(1), 49–63 (1977). DOI 10.1007/BF02761605

work page doi:10.1007/bf02761605 1977
[2]

Springer Monographs in Mathematics

Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Monographs in Mathematics. Springer, London (2009). DOI 10.1007/978-1-84800-998-1 COMPLETELY REACHABLE ROAD COLORING 15

work page doi:10.1007/978-1-84800-998-1 2009
[3]

In: Câmpeanu, C., Manea, F., Shallit, J

Bondar, E.A., V olkov, M.V .: Completely reachable automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) Descriptional Complexity of Formal Systems (DCFS 2016). Lect. Notes Com- put. Sci., vol. 9777, pp. 1–17. Springer, Cham (2016). DOI 10.1007/978-3-319-41114-9_1

work page doi:10.1007/978-3-319-41114-9_1 2016
[4]

Mat.-Fyz

ˇCerný, J.: Poznámka k homogénnym eksperimentom s koneˇcnými automatami. Mat.-Fyz. ˇCas. Slov. Akad. Vied14(3): 208–216 (1964). (In Slovak; English translation: A note on homo- geneous experiments with finite automata. J. Autom. Lang. Comb.24(2-4), 123–132 (2019). DOI 10.25596/jalc-2019-123)

doi:10.25596/jalc-2019-123 1964
[5]

MIT Press, Cambridge, MA (2022)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press, Cambridge, MA (2022)

2022
[6]

Electron

Don, H.: The ˇCerný conjecture and 1-contracting automata. Electron. J. Combin.23(3), 3–12 (2016). DOI 10.37236/5616

work page doi:10.37236/5616 2016
[7]

In: Etessami, K., Feige, U., Puppis, G

Ferens, R., Szykuła, M.: Completely reachable automata: A polynomial algorithm and qua- dratic upper bounds. In: Etessami, K., Feige, U., Puppis, G. (eds.) 50th International Collo- quium on Automata, Languages, and Programming (ICALP 2023). Leibniz Int. Proc. Inform., vol. 261, pp. 59:1-59:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). DOI...

work page doi:10.4230/lipics.icalp.2023.59 2023
[8]

ACM Trans

Ferens, R., Szykuła, M.: Recognizing completely reachable automata in quadratic time. ACM Trans. Algorithms22(2), 24:1-24:36 (2026). DOI 10.1145/3798283

work page doi:10.1145/3798283 2026
[9]

In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C

Hoffmann, S.: State complexity of the set of synchronizing words for circular automata and automata over binary alphabets. In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) Language and Automata Theory and Applications (LATA 2021). Lect. Notes Comput. Sci., vol. 12638, pp. 318–330. Springer, Cham (2021). DOI 10.1007/978-3-030-68195-1_25, ...

Pith/arXiv arXiv 2021
[10]

Technical Report PIBMRI-895.5-63, Dept

Laemmel, A.E.: Study on application of coding theory. Technical Report PIBMRI-895.5-63, Dept. Electrophysics, Microwave Research Inst., Polytechnic Inst. Brooklyn, NY (1963)

1963
[11]

In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Špánek, R., Turán, G

Maslennikova, M.I.: Reset complexity of ideal languages. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Špánek, R., Turán, G. (eds.) SOFSEM 2012, vol. II, pp. 33–44. Institute of Computer Science Academy of Sciences of the Czech Republic, Prague (2012), see also https://arxiv.org/abs/1404.2816

Pith/arXiv arXiv 2012
[12]

Ples ´nik, J.: The NP-completeness of the Hamiltonian cycle problem in planar diagraphs with degree bound two. Inform. Process. Lett.8(4), 199–201 (1979). DOI 10.1016/0020-0190(79) 90023-1

doi:10.1016/0020-0190(79 1979
[13]

Israel J

Trahtman, A.N.: The road coloring problem. Israel J. Math.172, 51–60 (2009). DOI 10.1007/ s11856-009-0062-5

2009
[14]

V olkov, M.V .: Synchronization of finite automata. Russ. Math. Surv.77(5), 819–891 (2022). DOI 10.4213/rm10005e

doi:10.4213/rm10005e 2022
[15]

Z.52, 642–648 (1950)

Wielandt, H.: Unzerlegbare, nicht negative Matrizen, Math. Z.52, 642–648 (1950). DOI 10. 1007/BF02230720

1950
[16]

In: Day, J.D., Manea, F

Zhu, Y .: Around Don’s conjecture for binary completely reachable automata. In: Day, J.D., Manea, F. (eds.), Developments in Language Theory (DLT 2024). Lect. Notes Comput. Sci., vol. 14791, pp. 282–295. Springer, Cham (2024). DOI 10.1007/978-3-031-66159-4_20

work page doi:10.1007/978-3-031-66159-4_20 2024

[1] [1]

Israel J

Adler, R.L., Goodwyn, L.W., Weiss, B.: Equivalence of topological Markov shifts. Israel J. Math.27(1), 49–63 (1977). DOI 10.1007/BF02761605

work page doi:10.1007/bf02761605 1977

[2] [2]

Springer Monographs in Mathematics

Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Monographs in Mathematics. Springer, London (2009). DOI 10.1007/978-1-84800-998-1 COMPLETELY REACHABLE ROAD COLORING 15

work page doi:10.1007/978-1-84800-998-1 2009

[3] [3]

In: Câmpeanu, C., Manea, F., Shallit, J

Bondar, E.A., V olkov, M.V .: Completely reachable automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) Descriptional Complexity of Formal Systems (DCFS 2016). Lect. Notes Com- put. Sci., vol. 9777, pp. 1–17. Springer, Cham (2016). DOI 10.1007/978-3-319-41114-9_1

work page doi:10.1007/978-3-319-41114-9_1 2016

[4] [4]

Mat.-Fyz

ˇCerný, J.: Poznámka k homogénnym eksperimentom s koneˇcnými automatami. Mat.-Fyz. ˇCas. Slov. Akad. Vied14(3): 208–216 (1964). (In Slovak; English translation: A note on homo- geneous experiments with finite automata. J. Autom. Lang. Comb.24(2-4), 123–132 (2019). DOI 10.25596/jalc-2019-123)

doi:10.25596/jalc-2019-123 1964

[5] [5]

MIT Press, Cambridge, MA (2022)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press, Cambridge, MA (2022)

2022

[6] [6]

Electron

Don, H.: The ˇCerný conjecture and 1-contracting automata. Electron. J. Combin.23(3), 3–12 (2016). DOI 10.37236/5616

work page doi:10.37236/5616 2016

[7] [7]

In: Etessami, K., Feige, U., Puppis, G

Ferens, R., Szykuła, M.: Completely reachable automata: A polynomial algorithm and qua- dratic upper bounds. In: Etessami, K., Feige, U., Puppis, G. (eds.) 50th International Collo- quium on Automata, Languages, and Programming (ICALP 2023). Leibniz Int. Proc. Inform., vol. 261, pp. 59:1-59:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). DOI...

work page doi:10.4230/lipics.icalp.2023.59 2023

[8] [8]

ACM Trans

Ferens, R., Szykuła, M.: Recognizing completely reachable automata in quadratic time. ACM Trans. Algorithms22(2), 24:1-24:36 (2026). DOI 10.1145/3798283

work page doi:10.1145/3798283 2026

[9] [9]

In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C

Hoffmann, S.: State complexity of the set of synchronizing words for circular automata and automata over binary alphabets. In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) Language and Automata Theory and Applications (LATA 2021). Lect. Notes Comput. Sci., vol. 12638, pp. 318–330. Springer, Cham (2021). DOI 10.1007/978-3-030-68195-1_25, ...

Pith/arXiv arXiv 2021

[10] [10]

Technical Report PIBMRI-895.5-63, Dept

Laemmel, A.E.: Study on application of coding theory. Technical Report PIBMRI-895.5-63, Dept. Electrophysics, Microwave Research Inst., Polytechnic Inst. Brooklyn, NY (1963)

1963

[11] [11]

In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Špánek, R., Turán, G

Maslennikova, M.I.: Reset complexity of ideal languages. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Špánek, R., Turán, G. (eds.) SOFSEM 2012, vol. II, pp. 33–44. Institute of Computer Science Academy of Sciences of the Czech Republic, Prague (2012), see also https://arxiv.org/abs/1404.2816

Pith/arXiv arXiv 2012

[12] [12]

Ples ´nik, J.: The NP-completeness of the Hamiltonian cycle problem in planar diagraphs with degree bound two. Inform. Process. Lett.8(4), 199–201 (1979). DOI 10.1016/0020-0190(79) 90023-1

doi:10.1016/0020-0190(79 1979

[13] [13]

Israel J

Trahtman, A.N.: The road coloring problem. Israel J. Math.172, 51–60 (2009). DOI 10.1007/ s11856-009-0062-5

2009

[14] [14]

V olkov, M.V .: Synchronization of finite automata. Russ. Math. Surv.77(5), 819–891 (2022). DOI 10.4213/rm10005e

doi:10.4213/rm10005e 2022

[15] [15]

Z.52, 642–648 (1950)

Wielandt, H.: Unzerlegbare, nicht negative Matrizen, Math. Z.52, 642–648 (1950). DOI 10. 1007/BF02230720

1950

[16] [16]

In: Day, J.D., Manea, F

Zhu, Y .: Around Don’s conjecture for binary completely reachable automata. In: Day, J.D., Manea, F. (eds.), Developments in Language Theory (DLT 2024). Lect. Notes Comput. Sci., vol. 14791, pp. 282–295. Springer, Cham (2024). DOI 10.1007/978-3-031-66159-4_20

work page doi:10.1007/978-3-031-66159-4_20 2024