Completely Reachable Road Coloring
July 13, 2026
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.
Introduction↩︎
Completely reachable automata are complete deterministic finite automata in which every nonempty subset of the state set occurs as the image of the whole state set under the action of some input word. Such automata arose in studies of the descriptional complexity of formal languages, first implicitly in [1] and later explicitly in [2].
In [2], Bondar and the first-named author posed three problems concerning completely reachable automata. The first was the problem of efficiently recognizing such automata: is there a polynomial-time algorithm that, given an automaton \(\mathrsfs{A}\), determines whether \(\mathrsfs{A}\) is completely reachable? This question was recently answered in the affirmative by Ferens and Szykuła [3], [4]. The other two problems were inspired by well-known questions in the theory of synchronizing automata, of which completely reachable automata form a special class.
In connection with the Černý conjecture (cf. [5]), it was suggested in [2] to investigate the following question: if \(\mathrsfs{A}\) is a completely reachable automaton with \(n\) states, how can the length of a shortest word with an \(m\)-element image (\(1\le m<n\)) be upper-bounded in terms of \(n\) and \(m\)? Don’s conjecture [6], according to which \(n(n-m)\) is such an upper bound, was refuted by the second-named author [7]; on the other hand, Ferens and Szykuła [4] obtained the upper bound \[2n(n-m)-n(1+\frac{1}{2}+\cdots+\frac{1}{n-m}).\]
Motivated by the Road Coloring Conjecture of Adler, Goodwyn, and Weiss [8], subsequently proved by Trahtman [9], it was asked in [2] which digraphs admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph becomes a completely reachable automaton. This is the question we address in the present note, thereby completing the research program proposed in [2].
We assume that the reader is familiar with basic concepts of computational complexity such as polynomial-time reduction and NP-completeness.
1 Background and overview↩︎
1.1 Automata↩︎
All automata in this note are complete, deterministic, and finite. Such an automaton (a DFA) is a pair \((Q,\Sigma)\) of finite nonempty sets equipped with a map \(Q\times\Sigma\to Q\). The elements of \(Q\) and \(\Sigma\) are referred to as states and letters, respectively. The map \(Q\times\Sigma\to Q\) is called the action of letters on states. For a state \(q\in Q\) and a letter \(a\in\Sigma\), the result of the action of \(a\) on \(q\) is denoted by \(q{\cdot}a\).
A word over \(\Sigma\) is a finite sequence of letters. We allow the empty word, denoted by \(\varepsilon\), which is the empty sequence. The set of all words over \(\Sigma\) is denoted by \(\Sigma^*\). For \(q\in Q\) and \(w\in\Sigma^*\), the action of \(w\) on \(q\) in \((Q,\Sigma)\) is defined recursively by \[q{\cdot}w:=\begin{cases} q & \text{if } w=\varepsilon,\\ (q{\cdot}w'){\cdot}a & \text{if } w=w'a \text{ for some } w'\in\Sigma^* \text{ and } a\in\Sigma, \end{cases}\] and the action of \(w\) on a nonempty subset \(P\subseteq Q\) is defined by \[P{\cdot}w:=\{p{\cdot}w : p\in P\}.\]
A subset \(P \subseteq Q\) is called reachable in \((Q,\Sigma)\) if there exists a word \(w \in \Sigma^*\) such that \(P = Q{\cdot}w\). A DFA is completely reachable if every nonempty subset of its state set is reachable. A DFA \((Q,\Sigma)\) is synchronizing if some one-element subset \(\{q\}\) is reachable in \((Q,\Sigma)\). Obviously, every completely reachable automaton is synchronizing.
1.2 Digraphs and colorings↩︎
A digraph is a quadruple \((V,E,s,t)\), where \(V\) and \(E\) are sets and \(s,t\colon E\to V\) are functions. The elements of \(V\) and \(E\) are called vertices and edges, respectively. For an edge \(e\in E\), the vertices \(s(e)\) and \(t(e)\) are called the source and the target of \(e\), respectively, and we say that \(e\) is an edge from \(s(e)\) to \(t(e)\). Note that, under this definition, for any \(u,v\in V\), there may be several edges from \(u\) to \(v\); we call such edges parallel.
A path of length \(\ell\) from \(u\) to \(v\) is an alternating sequence \[u_0,e_1,u_1,e_2,\dots,u_{\ell-1},e_\ell,u_\ell\] of vertices \(u_0,u_1,\dots,u_\ell\) and edges \(e_1,\dots,e_\ell\) such that \(u=u_0\), \(v=u_\ell\), \(s(e_i)=u_{i-1}\), and \(t(e_i)=u_i\) for all \(i=1,\dots,\ell\). A digraph is strongly connected if, for every pair of distinct vertices \(u,v\), there exists a path from \(u\) to \(v\).
A labeling of a digraph \((V,E)\) with label set \(\Lambda\) is a map \(E\to\Lambda\).
For a set \(\Sigma\), let \(\mathop{\mathrm{\mathcal{P}}}'(\Sigma)\) denote the set of all nonempty subsets of \(\Sigma\). An arbitrary DFA \((Q,\Sigma)\) can be represented as a labeled digraph with vertex set \(Q\), edge set \[E:=\{(p,q)\in Q\times Q : (\exists\, a\in\Sigma)\, p{\cdot}a=q \},\] the functions \(s,t\colon E\to V\) defined by \(s(p,q):=p\), \(t(p,q)=q\), and labeling \(E\to\mathop{\mathrm{\mathcal{P}}}'(\Sigma)\) defined by \((p,q)\mapsto\{a\in\Sigma: p{\cdot}a=q \}\). For an illustration, Fig. 1 shows the labeled digraph of the Černý automaton \(\mathrsfs{C}_4\) [10], which has states \(0,1,2,3\), letters \(a,b\), and the action of letters on states defined by \[0{\cdot}a=0{\cdot}b:=1,\;\;m{\cdot}a:=m,\;\;m{\cdot}b:=m+1\mkern-12mu\pmod 4 \;\text{for } m=1,2,3.\]
(In Fig. 1 and below we omit { } in the edge labels.)
The digraph obtained from the labeled digraph of a DFA \(\mathrsfs{A}\) by omitting the labels is called the underlying digraph of \(\mathrsfs{A}\). We shall call a DFA strongly connected whenever its underlying digraph is strongly connected.
Due to completeness and determinism, in the labeled digraph of a DFA \((Q,\Sigma)\), the labels of edges with a common source form a partition of \(\Sigma\). This observation admits a converse in the following sense. Suppose that a labeling \(\alpha\) of a digraph \(G=(V,E,s,t)\) assigns nonempty subsets of a set \(\Sigma\) to edges in such a way that, for every vertex \(v\in V\), the family \(\{\alpha(e): s(e)=v\}\) forms a partition of \(\Sigma\); such a labeling is called a road coloring. Every road coloring \(\alpha\) defines an action of \(\Sigma\) on \(V\): for \(v\in V\) and \(a\in\Sigma\), set \(v{\cdot}a:=t(e)\), where \(e\) is the unique edge such that \(s(e)=v\) and the set \(\alpha(e)\) contains \(a\). We thus obtain a DFA, referred to as a coloring of the digraph \(G\) and denoted by \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\).
1.3 Road coloring problems and our contribution↩︎
Given a class \(\mathbf{C}\) of automata, one may ask for which digraphs \(G\) there exists a road coloring \(\alpha\) the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) belongs to \(\mathbf{C}\). One may also ask for which digraphs \(G\) every road coloring \(\alpha\) is such that the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) belongs to \(\mathbf{C}\). We will refer to these questions as the road coloring problem (RCP) and the universal road coloring problem, respectively, for the class \(\mathbf{C}\).
With this terminology, the famous Road Coloring Conjecture of Adler, Goodwyn, and Weiss [8], confirmed by Trahtman [9], concerns the RCP for the class \(\mathbf{SCS}\) of strongly connected synchronizing automata. The name of the problem stems from the following property of strongly connected synchronizing automata which admits a ‘practical’ interpretation. In every strongly connectedsynchronizing automaton\(\mathrsfs{A}=(Q,\Sigma)\), one can assign to each state \(q\in Q\) a word \(w_q\in\Sigma^*\) such that, by following the path whose labels spell \(w_q\), one is guaranteed to arrive at \(q\) from any initial state. Indeed, since \(\mathrsfs{A}\) is synchronizing, there exist a state \(p\in Q\) and a word \(u\in\Sigma^*\) such that \(Q{\cdot}u=\{p\}\); since \(\mathrsfs{A}\) is strongly connected, there exists a word \(v\in\Sigma^*\) such that \(p{\cdot}v=q\). Then the word \(uv\) has the desired property that \(r{\cdot}uv=q\) for every \(r\in Q\).
Suppose now that a bus carrying tourists arrives in a city and parks at some location. The tourists are then free to explore the city on their own, after which they must return to the bus. If the city’s map can be colored into a synchronizing automaton, then every tourist can find their way back to the bus from wherever they happen to be by following the same sequence of colors, determined solely by the location where the bus is parked.
The mathematical motivation for the Road Coloring Conjecture in [8] came from a question in symbolic dynamics, but in [8], the authors were able to resolve that question by a different route, bypassing the conjecture altogether. We believe that road coloring problems are interesting per se, even without external motivation, as a kind of ‘reverse engineering’ of automata: we aim to understand the extent to which certain important properties of automata are determined by their underlying digraphs.
We consider the RCP for the class \(\mathbf{CR}\) of completely reachable automata. It also admits a ‘practical’ interpretation. Think of a digraph as a network of roads connecting service centers, each staffed by an emergency-response team. Suppose that, for some reason, only a certain subset of centers needs to remain operational, while all other teams should be redeployed there. If the digraph admits a completely reachable road coloring, then there is a uniform instruction—a sequence of colors to be followed simultaneously by all teams—that will relocate the teams so that, in the end, exactly the designated centers remain occupied.
Although completely reachable automata form a subclass of strongly connected synchronizing automata, our solution to the RCP for completely reachable automata is not a specialization of Trahtman’s. Indeed, a criterion guaranteeing that a coloring of a DFA belongs to a class \(\mathbf{C}\) of automata yields, for a subclass \(\mathbf{C}'\subset\mathbf{C}\), only a necessary condition for membership in \(\mathbf{C}'\). Moreover, it was already observed in [2] that the RCPs for \(\mathbf{SCS}\) and \(\mathbf{CR}\) differ essentially. Trahtman’s result implies that the number of colors plays no role in the case \(\mathbf{SCS}\): if a strongly connected digraph \(G\) admits a synchronizing coloring, then it also admits one with the minimum possible number of colors, namely, the maximum out-degree of the vertices of \(G\). In contrast, [2], reproduced below as Fig. 2, presents a digraph that has no completely reachable coloring with 2 letters but does admit such a coloring with 3 letters.
We give a combinatorial characterization of digraphs admitting a completely reachable coloring in Theorem 1; this characterization can be verified in polynomial time. On the other hand, Theorem 2 shows that, for every fixed \(k\ge 2\), the problem of deciding whether a given digraph admits a completely reachable coloring with \(k\) colors is NP-complete. Our final result, Theorem 3, solves the universal road coloring problem for the class \(\mathbf{CR}\). To the best of our knowledge, this problem remains open for the class of synchronizing automata—no combinatorial characterization is known for totally synchronizing digraphs, that is, digraphs all of whose colorings are synchronizing.
2 Colorings with unrestricted number of colors↩︎
A path \(u_0,e_1,u_1,\dots,e_\ell,u_\ell\) in a digraph \(G=(V,E,s,t)\) is called a cycle if \(u_\ell=u_0\). The period of \(G\) is the greatest common divisor of the lengths of all cycles in \(G\). A digraph is aperiodic if its period is equal to \(1\). For a subset \(T\subseteq V\), the inflow of \(T\) in \(G\) is the set \(\mathop{\mathrm{In}}_G(T):=\{s(e) : e\in E\;\text{ and }\;t(e)\in T\}\), that is, the set of sources of all edges whose targets lie in \(T\). A subset \(T\subseteq V\) is absorbing if \(|T|\le|\mathop{\mathrm{In}}_G(T)|\).
Theorem 1. A digraph \(G=(V,E)\) admits a completely reachable coloring if and only if \(G\) is strongly connected, aperiodic, and every subset of \(V\) is absorbing. These conditions can be verified in time polynomial in \(|V|\), \(|E|\).
Proof. Necessity. Suppose \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)=(V,\Sigma)\) is a completely reachable coloring of \(G\).
For any two vertices \(p,q\in V\), if \(w\in\Sigma^*\) satisfies \(V{\cdot}w=\{q\}\), then \(p{\cdot}w=q\). Therefore, the path in \(G\) whose labels in \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) spell \(w\) connects \(p\) to \(q\). Hence, \(G\) is strongly connected. Moreover, since the one-element subset \(\{q\}\) is reachable, the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) is synchronizing. That the underlying digraph of any strongly connected synchronizing automaton is aperiodic was already shown in Laemmel’s report [11], one of the earliest texts about synchronizing automata, and rediscovered in [8]. Hence, \(G\) is aperiodic.
It remains to verify that every subset \(T\subseteq V\) is absorbing. This is clear if \(T\) is empty. As \(G\) is the underlying digraph of a DFA, each vertex of \(G\) is the source of an edge. Hence, the inflow of \(V\) is \(V\), and \(V\) is absorbing. Now let \(T\) be a proper nonempty subset. Since the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) is completely reachable, \(T=V{\cdot}w\) for some word \(w\) that can be written as \(w=w'a\) with \(w'\in\Sigma^*\) and \(a\in\Sigma\). Let \(S:=V{\cdot}w'\). Then \(S{\cdot}a=T\), which means that every vertex \(t\in T\) is the target of an edge labeled \(a\) in \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) whose source lies in \(S\). Hence \(S\subseteq \mathop{\mathrm{In}}_G(T)\), and since \(|T|\le|S|\), the set \(T\) is absorbing.
Complexity. Algorithms for verifying the strong connectivity and finding the period of a digraph \(G=(V,E,s,t)\) in time \(O(|V|+|E|)\) are well known; see, for example, [12], Sects. 5.2 and 17.8, respectively. Using these algorithms, one can check in time \(O(|V|+|E|)\) whether \(G\) is strongly connected and aperiodic.
To check if every subset of \(V\) is absorbing, we use the bipartite representation \(BP(G)\) of \(G\). This is the bipartite graph \((V',V'',F)\) with parts \(V':=\{v': v\in V\}\) and \(V'':=\{v'': v\in V\}\) and edge set \[F:=\bigl\{(u',w'')\in V'\times V'' : (\exists\, e\in E)\, s(e)=w \land t(e)=u\bigr\};\] see Fig. 3 for an illustration.
For a subset \(T\subseteq V\), we denote by \(T'\) and \(T''\) its copies in the parts \(V'\) and \(V''\), respectively, and for a subset \(U\subseteq V'\), we denote by \(N(U)\) the set of vertices in \(V''\) that are adjacent to at least one vertex in \(U\). By construction, \(N(T')=\mathop{\mathrm{In}}_G(T)''\) for every subset \(T\subseteq V\). Therefore \(T\) is absorbing if and only if \(|T'|\le|N(T')|\). Hence, every subset of \(V\) is absorbing if and only if \(|U|\le|N(U)|\) for every \(U\subseteq V'\). By Hall’s marriage theorem (see [12]), this is precisely the condition for the graph \(BP(G)\) to admit a matching that covers \(V'\). (Recall that a matching in a bipartite graph \(B\) is a set of edges without common vertices; a matching \(M\) covers a part of \(B\) if each vertex of this part appears in an edge from \(M\).) The existence of such a matching can be decided in \(O(\sqrt{|V|}|E|)\) time using the Hopcroft–Karp algorithm [13].
Sufficiency. We again use the bipartite graph \(BP(G)\). For each nonempty subset \(W\subseteq V\), consider the induced subgraph \(H\) of \(BP(G)\) with vertex set \(W'\cup\mathop{\mathrm{In}}_G(W)''\). Since every subset of \(V\) is absorbing, we have \(|U|\le|N(U)|\) for every \(U\subseteq W'\). Clearly, \(N(W')\subseteq \mathop{\mathrm{In}}_G(W)''\), and therefore the graph \(H\) satisfies the condition of Hall’s marriage theorem. Hence, \(H\) admits a matching that covers \(W'\). Fix such a matching \(M\) and define a function \(f_W\colon V''\to V'\) as follows:
if \(x\) is covered by an edge \((x,y)\in M\), then \(f_W(x):=y\);
if \(x\in \mathop{\mathrm{In}}_G(W)''\) is not covered by the matching \(M\), then \(f_W(x)\) is an arbitrary vertex in \(W'\) adjacent to \(x\);
if \(x\in V''\setminus \mathop{\mathrm{In}}_G(W)''\), then \(f_W(x)\) is an arbitrary vertex in \(V'\) adjacent to \(x\).
By construction, \(W'=f_W(\mathop{\mathrm{In}}_G(W)'')\).
Define a labeling \(\alpha\colon E\to\mathop{\mathrm{\mathcal{P}}}'(\Sigma)\), where \(\Sigma:=\mathop{\mathrm{\mathcal{P}}}'(V)\), by \[\alpha(e):=\{U\in\Sigma: f_U(s(e)'')=t(e)'\}.\] By construction, for every \(v\in V\), the set \(\alpha(e)\), where \(s(e)=v\), contains \(U\in\Sigma\) if and only if \(f_U(v'')=t(e)'\). Hence, the family \(\{\alpha(e): s(e)=v\}\) forms a partition of \(\Sigma\), i.e., \(\alpha\) is a road coloring. We thus obtain the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)=(V,\Sigma)\), in which the vertices of \(V\) are the states and the nonempty subsets of \(V\) are the letters. Clearly, in \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) we have \[\label{eq:selfmap} \mathop{\mathrm{In}}_G(U){\cdot}U = U\tag{1}\] for every nonempty subset \(U\subseteq V\). (On the left-hand side of 1 \(U\) occurs as a letter from \(\Sigma\) acting on the set \(\mathop{\mathrm{In}}_G(U)\); on the right-hand side, \(U\) occurs as a set of states.)
By Wielandt’s theorem [14], in every strongly connected aperiodic digraph with \(n\) vertices, there exists a path of length \((n-1)^2+1\) between every two vertices. If, for an arbitrary nonempty subset \(U_0\subseteq V\), we define \(U_\ell:= \mathop{\mathrm{In}}_G(U_{\ell-1})\) for all \(\ell\ge 1\), then \(U_\ell\) contains all vertices \(w\) for which there exists a path of length \(\ell\) between \(w\) and a vertex of \(U_0\). Hence \(U_k = V\), where \(k:=(|V|-1)^2+1\). From 1 , it follows that \[V{\cdot}U_{k-1} U_{k-2} \cdots U_1 U_0=U_0,\] in particular, the subset \(U_0\) is reachable. Hence, the DFA \(\mathop{\mathrm{\mathrsfs{A}}}\) is completely reachable, and the digraph \(G\) admits a completely reachable coloring. ◻
For a given digraph \(G=(V,E,s,t)\), the completely reachable coloring constructed in Theorem 1 uses \(2^{|V|-1}\) colors. Of course, this number of colors is far from optimal. However, as the result of the next section shows, the problem of finding a completely reachable coloring with the minimum number of colors is computationally hard.
3 Colorings with restricted number of colors↩︎
Theorem 2. For each \(k\ge 2\), determining whether a given digraph admits a completely reachable coloring with \(d\) colors is NP-complete.
That the problem belongs to NP is easy to see: if one nondeterministically guesses a completely reachable coloring with \(k\) colors, Ferens–Szykuła’s algorithm [4] can verify the guess in polynomial time.
For the hardness proof, we use a variant of the classical Hamiltonian cycle problem. We say that a cycle \(C\) in a digraph \(G = (V,E,s,t)\) is Hamiltonian if the length of \(C\) is equal to \(|V|\) and every vertex of \(V\) occurs in \(C\). In [15], Plesńik constructed a polynomial-time reduction from the Boolean satisfiability problem SAT to the problem of determining whether a digraph from a special class has a Hamiltonian cycle. We will show that every digraph \(G\) from Plesńik’s class can be transformed in polynomial time into a digraph \(\overline{G}\) such that \(G\) has a Hamiltonian cycle if and only if \(\overline{G}\) admits a completely reachable coloring with \(k\emph{}\) colors. Since SAT is NP-complete, this establishes the NP-hardness of our problem.
We need some notions and notation. For a vertex \(v\) of a digraph \(G=(V,E,s,t)\), its out-degree \(\mathop{\mathrm{deg}}_G^+(v)\) is the number of edges \(e\in E\) such that \(s(e)=v\), and its in-degree \(\mathop{\mathrm{deg}}_G^-(v)\) is the number of edges \(e\in E\) such that \(t(e)=v\). A digraph \(G=(V,E)\) is \(k\)-out-regular if \(\mathop{\mathrm{deg}}_G^+(v)=k\) for all \(v\in V\). For a DFA \(\mathop{\mathrm{\mathrsfs{A}}}= (Q,\Sigma)\), the defect of a letter \(a \in \Sigma\) is the number \(\mathop{\mathrm{dfc}}(a):=|Q| - |Q{\cdot}a|\).
Lemma 1. Let \(G =(V,E,s,t)\) be a \(k\)-out-regular digraph and \(\alpha\) a road coloring of \(G\) with color set \(\Sigma\) of size \(k\). Then in the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G, \alpha)\), \[\sum_{a \in \Sigma} \mathop{\mathrm{dfc}}(a)\ge \sum_{v \in V} \max\{0, (k - \mathop{\mathrm{deg}}_G^-(v))\}.\]
Proof. Since \(|\Sigma| = k\) and \(G\) is \(k\)-out-regular, each set \(\alpha(e)\) is a singleton, because for every vertex \(v\), the sets \(\{\alpha(e): s(e)=v\}\) partition \(\Sigma\).
For each \(a \in \Sigma\), let \(G_a\) be the subdigraph of \(G\) whose vertex set is \(V\) and whose edge set consists of all edges \(e\) with \(\alpha(e)=\{a\}\). For every vertex \(v\), we have \[\left| \{a \in \Sigma : \mathop{\mathrm{deg}}_{G_a}^-(v) = 0\} \right|+ \left| \{a \in \Sigma : \mathop{\mathrm{deg}}_{G_a}^-(v) > 0\} \right| = |\Sigma|=k,\] and the summand \(\left| \{a \in \Sigma : \mathop{\mathrm{deg}}_{G_a}^-(v) > 0\} \right|\) does not exceed \(\mathop{\mathrm{deg}}_G^-(v)\). Hence \[\left| \{a \in \Sigma : \mathop{\mathrm{deg}}_{G_a}^-(v) = 0\} \right| \ge \max\{0, (k - \mathop{\mathrm{deg}}_G^-(v))\},\] since the left-hand side is nonnegative. Summing up over all \(v\in V\) yields \[\sum_{v \in V} \left| \{a \in \Sigma : \mathop{\mathrm{deg}}_{G_a}^-(v) = 0\} \right| \ge \sum_{v \in V}\max\{0, (k - \mathop{\mathrm{deg}}_G^-(v))\},\] and the sum in the left-hand side is equal to \(\sum_{a \in \Sigma}\mathop{\mathrm{dfc}}(a)\) since, clearly, \(\mathop{\mathrm{dfc}}(a)\) equals the number of vertices with in-degree \(0\) in \(G_a\). ◻
We now identify a class of digraphs for which Hamiltonicity is equivalent to the existence of a completely reachable coloring with a prescribed number of colors.
Lemma 2. Let \(k \ge 2\) and let \(G = (V,E,s,t)\) be a \(k\)-out-regular digraph with a prime number of vertices greater than \(\max\{3,k\}\). Suppose that there exists a vertex \(x\in V\) such that, for every \(v\in V\), there are at least \(k-2\) edges from \(v\) to \(x\), and that deleting \(k-2\) edges from \(v\) to \(x\) from \(E\) for each \(v\in V\) yields a digraph \(G'\) in which
\(\mathop{\mathrm{deg}}_{G'}^-(x) = 1\),
there exists a vertex \(y\) such that \(\mathop{\mathrm{deg}}_{G'}^-(y) = 3\),
for each \(z \in V \setminus \{x,y\}\), \(\mathop{\mathrm{deg}}_{G'}^-(z) = 2\).
Then \(G\) admits a completely reachable coloring with \(k\) colors if and only if \(G\) has a Hamiltonian cycle.
Proof. Necessity. Let \(\alpha\) be a completely reachable coloring of \(G\) with color set \(\Sigma\) of size \(k\), and let \(n=|V|\). Every \((n-1)\)-element subset of \(V\) must be reachable in the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)=(V,\Sigma)\). This implies that \(\Sigma\) contains letters of defect \(1\). If \(P=V{\cdot}w\) for some word \(w=w'c\) with \(w'\in\Sigma^*\) and \(c\in\Sigma\), then \(P\subseteq V{\cdot}c\). Therefore, if \(\Sigma\) contained no letters of defect \(0\), then words reaching distinct \((n-1)\)-element subsets of \(V\) would have distinct last letters. Since there are \(n\) such subsets and only \(k<n\) letters, this is impossible. Hence, \(\Sigma\) contains a letter of defect \(0\). Denote it by \(a\). We claim that no further letter has defect 0 and exactly one letter has defect \(1\).
Indeed, by Lemma 1, we have \[\sum_{b \in \Sigma}\mathop{\mathrm{dfc}}(b) \ge \sum_{v \in V} \max(0, k - \mathop{\mathrm{deg}}_G^-(v)) \ge \sum_{v \in V\setminus\{x\}} \max(0, k - \mathop{\mathrm{deg}}_G^-(v)).\] Conditions imposed on the digraph \(G\) imply that \(\mathop{\mathrm{deg}}_{G}^-(y) = \mathop{\mathrm{deg}}_{G'}^-(y) = 3\) and \(\mathop{\mathrm{deg}}_{G}^-(z) = \mathop{\mathrm{deg}}_{G'}^-(z) = 2\) for each \(z \in V \setminus \{x,y\}\). Therefore the sum on the right-hand side equals \((n-2)(k-2)+k-3=(n-1)(k-2)-1\). Now assume that there exist two letters \(c,d\ne a\) of defect 0 or 1. Since the defect of any letter does not exceed \(n-1\), \[\begin{gather} \sum_{b \in \Sigma}\mathop{\mathrm{dfc}}(b) = \sum_{b\ne a,c,d}\mathop{\mathrm{dfc}}(b) + \mathop{\mathrm{dfc}}(a) + \mathop{\mathrm{dfc}}(c) + \mathop{\mathrm{dfc}}(d) \le \\ (n-1)(k-3) + 0 + 1 + 1 = (n-1)(k-2) - (n-3). \end{gather}\] Since \(n\ge 5\), we have \(-1>-(n-3)\), and hence the inequalities \[\sum_{b \in \Sigma}\mathop{\mathrm{dfc}}(b) \ge (n-1)(k-2)-1\; \text{ and }\;\sum_{b \in \Sigma}\mathop{\mathrm{dfc}}(b) \le (n-1)(k-2) - (n-3)\] contradict each other.
Proposition 3 of [16] states that if an \(n\)-state DFA \((Q,\Theta)\) has \(m<n\) letters of defect 1 and every \((n-1)\)-element subset of \(Q\) is reachable, then the group of transformations on \(Q\) generated by the letters of defect 0 has at most \(m\) orbits. Applied to the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\), where, as we have shown, the group is generated by \(a\) and \(m=1\), this implies that \(a\) is a cyclic permutation of the vertices in \(V\). Hence, the edges labeled \(a\) form a Hamiltonian cycle.
Sufficiency. First observe that since the digraph \(G\) is \(k\)-out-regular and, when passing to \(G'\), we remove \(k-2\) edges from \(v\) to \(x\) for each \(v\in V\), the digraph \(G'\) is \(2\)-out-regular.
Now let \(C\) be a Hamiltonian cycle in the digraph \(G\) and let \(D\) be the set of edges of the subdigraph \(G'\) that do not belong to \(C\). The vertex \(x\) is the target of exactly one edge \(e_x\) of \(C\). If this edge is not among those removed when passing to \(G'\), then every edge of \(C\) is in \(G'\). We label the edges of \(C\) and \(D\) by the letters \(c\) and \(d\), respectively. This road colors the digraph \(G'\) into the DFA \((V,\{c,d\})\), in which \(c\) acts as a cyclic permutation and \(d\) has defect 1, since \(V\setminus V{\cdot}d=\{x\}\). It follows from [2] that a DFA with a prime number of states is completely reachable whenever it has a letter that acts as a cyclic permutation and a letter of defect 1. Therefore, the DFA \((V,\{c,d\})\) is completely reachable. Clearly, if we extend this road coloring of \(G'\) to a road coloring \(\alpha\) of the digraph \(G\), then the DFA \(\mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\) is also completely reachable.
Now assume that the edge \(e_x\) was removed when passing to \(G'\). The other \(n-1\) edges of \(C\) remain in \(G'\), whence \(|D|=n+1\). Fix a vertex \(z\ne x,y\). Then \(\mathop{\mathrm{deg}}_{G'}^-(z) = 2\), that is, there are two edges in \(G'\) with target \(z\), one in \(C\) and one in \(D\). Let \(e\) be the edge in \(D\) with \(t(e)=z\) and let \(G''\) be the digraph with vertex set \(V\) and edge set \(C\cup(D\setminus\{e\})\). We label the edges of \(C\) and \(D\setminus\{e\}\) by the letters \(c\) and \(d\), respectively. This road colors the digraph \(G''\) into the DFA \((V,\{c,d\})\), in which \(c\) acts as a cyclic permutation and \(d\) has defect 1, since \(V\setminus V{\cdot}d=\{z\}\). As above, [2] implies that the DFA \((V,\{c,d\})\) is completely reachable, and this road coloring of \(G''\) extends to a completely reachable road coloring of the digraph \(G\). ◻
Proof of Theorem 2. Plesńik [15] constructed, for an arbitrary Boolean formula \(F\) in conjunctive normal form, a digraph \(G =(V,E,s,t)\) such that
\(|V|\) and \(|E|\) are polynomial in the numbers of variables and clauses of \(F\),
for every vertex \(v\in V\), either \(\mathop{\mathrm{deg}}_G^-(v)=1\) and \(\mathop{\mathrm{deg}}_G^+(v)=2\), or \(\mathop{\mathrm{deg}}_G^-(v)=2\) and \(\mathop{\mathrm{deg}}_G^+(v)=1\),
every edge joins a vertex of out-degree \(1\) to a vertex of in-degree \(1\), or a vertex of out-degree \(2\) to a vertex of in-degree \(2\), and
\(F\) is satisfiable if and only if \(G\) has a Hamiltonian cycle.
The digraph \(G\) in Plesńik’s construction is also planar, but planarity is not needed for the argument below. Adding a parallel edge to each edge that joins a vertex of out-degree \(1\) to a vertex of in-degree \(1\) does not affect the presence or absence of a Hamiltonian cycle. Consequently, one may replace digraphs satisfying conditions (i)–(iv) by digraphs satisfying (i), (iv), and
- \(\mathop{\mathrm{deg}}_G^-(v)=\mathop{\mathrm{deg}}_G^+(v)=2\) for every vertex \(v\in V\).
In view of the NP-completeness of the Boolean satisfiability problem, it suffices to show that, for each \(k\ge 2\), any digraph \(G\) satisfying (v) can be transformed, in polynomial time, into a digraph to which Lemma 2 applies.
Our transformation uses the following operation on digraphs. If \(D = (V_D, E_D, s_D, t_D)\) and \(H = (V_H, E_H, s_H, t_H)\) are two digraphs with disjoint vertex and edge sets, \(v\) is a vertex of \(D\), and \(x_1,x_2\) are two distinct vertices in \(H\), we define the digraph \(\mathop{\mathrm{Repl}}(D,\frac{v}{x_1,x_2},H)\) as \((V_R,E_R,s_R,t_R)\), where \(V_R:=(V_D\setminus \{v\}) \cup V_H\), \(E_R:=E_D \cup E_H\), and the functions \(s_R\) and \(t_R\) are defined by \[\begin{align} s_R(e)&: = \begin{cases} s_D(e) & \text{if e \in E_D and s_D(e) \neq v},\\ s_H(e) & \text{if e \in E_H},\\ x_1 & \text{otherwise}, \end{cases}\\ t_R(e)&: = \begin{cases} t_D(e) & \text{if e \in E_D and t_D(e) \neq v},\\ t_H(e) & \text{if e \in E_H},\\ x_2 & \text{otherwise.} \end{cases} \end{align}\]
A digraph to which Lemma 2 applies must contain a subdigraph \(G'\) with two vertices \(x\) and \(y\) having in-degrees \(1\) and \(3\), respectively, while every other vertex satisfies \(\mathop{\mathrm{deg}}_{G'}^-(z)=2\). To achieve this, we use the funnel digraph \(F_3\) with three vertices \(x,y,x_1\) and four edges: two from \(x\), one to \(y\) and one to \(x_1\), and two from \(y\), one to \(x\) and one to \(x_1\); see Fig. 4.
Take an arbitrary digraph \(G\) satisfying (v), choose any vertex \(v_0\) of \(G\), and define \(G_1:= \mathop{\mathrm{Repl}}(G, \frac{v_0}{x_1,y},F_3)\). The transformation \(G\rightsquigarrow G_1\) is illustrated in Fig. 5.
Clearly, \(\mathop{\mathrm{deg}}_{G_1}^-(x) = 1\), \(\mathop{\mathrm{deg}}_{G_1}^-(y) = 3\), and \(\mathop{\mathrm{deg}}_{G_1}^-(z) = 2\) for each \(z \ne x,y\); besides that, it is easy to see that \(G_1\) is 2-out-regular and has a Hamiltonian cycle if and only if so does \(G\).
The next property we need to ensure to be able to apply Lemma 2 is the primality of the number of states. For this, for each positive integer \(m\), consider the double line digraph \(L_m\) with vertex set \(\{y_1, \ldots, y_{m+1}\}\) that has two edges from \(y_i\) to \(y_{i+1}\) for all \(1 \le i \le m\). Choose \(m\) as the least positive integer such that \(m + |V_{G_1}|\) is a prime number and let \(G_2 := \mathop{\mathrm{Repl}}(G_1, \frac{x_1}{y_1,y_{m+1}},L_m)\). The transformation \(G_1\rightsquigarrow G_2\) is illustrated in Fig. 6.
Obviously, the digraph \(G_2\) retains all properties of \(G_1\)—it is a 2-out-regular digraph such that \(\mathop{\mathrm{deg}}_{G_2}^-(x) = 1\), \(\mathop{\mathrm{deg}}_{G_2}^-(y) = 3\), and \(\mathop{\mathrm{deg}}_{G_2}^-(z) = 2\) for each \(z \in V_{G_2}\setminus \{x,y\}\), and it has a Hamiltonian cycle if and only if so does \(G_1\). Besides, the number of states of \(G_2\) is prime.
Define \(G_3\) to be the digraph obtained from \(G_2\) by adding \(k-2\) edges from \(v\) to \(x\) for every vertex \(v\in V_{G_2}\). Then \(G_3\) has a Hamiltonian cycle if and only if \(G_2\) has a Hamiltonian cycle and \(G_3\) fulfills all conditions of Lemma 2 (with the subdigraph \(G_2\) in the role of \(G'\)). Lemma 2 now implies that the digraph \(G_3\) is completely reachable if and only if the initial digraph \(G\) satisfying (v) has a Hamiltonian cycle. The described transformation \(G\rightsquigarrow G_3\) requires time polynomial in the size of \(G\) since the least prime greater than a given positive integer \(n\) does not exceed \(2n\) by Bertrand’s postulate, and the sieve of Eratosthenes can be used to find this prime in \(O(n\log\log n)\) time. ◻
4 Digraphs satisfying all road colorings are completely reachable↩︎
For a vertex \(u\) of a digraph \(G\), its out-neighbor is any vertex \(v\) such that \(G\) has an edge from \(u\) to \(v\).
Lemma 3. A digraph \(G=(V,E,s,t)\) all of whose colorings are completely reachable has a unique vertex with more than one out-neighbor and contains a Hamiltonian cycle.
Proof. By Theorem 1, the digraph \(G\) is strongly connected. Then every vertex has at least one out-neighbor. Assume that there exist two distinct vertices \(u\) and \(v\) with at least two out-neighbors each.
Consider the bipartite representation \(BP(G)=(V',V'',F)\) of \(G\). As established in the proof of Theorem 1, there is a matching \(M\subset F\) that covers \(V'\). By the choice of \(u\) and \(v\), each of the vertices \(u''\) and \(v''\) is incident with at least two edges of \(F\). Hence there exist out-neighbors \(u_1\) and \(v_1\) of \(u\) and \(v\), respectively, such that the edges \((u'_1,u'')\) and \((v'_1,v'')\) do not belong to \(M\). (We do not claim that \(u_1\ne v_1\); the argument below works equally well when \(u_1=v_1\).) Using this, it is easy to see that for every edge \(f=(x_1,x_2)\in F\setminus M\), there exists an edge \((y_1,y_2)\in F\setminus M\) such that \(y_2\ne x_2\). Indeed, either \(x_2\ne u''\) or \(x_2\ne v''\), and one can take \((u'_1,u'')\) or \((v'_1,v'')\), respectively, as \((y_1,y_2)\). Now let \(M_f\) be the subset of \(F\) obtained from \(M\) by replacing the edges of \(M\) incident to \(x_1\) and \(y_1\) with the edges \(f=(x_1,x_2)\) and \((y_1,y_2)\), respectively. (If \(x_1=y_1\), then only one edge is removed, but still two are added.)
Let \(\mathcal{M} := \{M\} \cup \{M_f : f \in F \setminus M\}\). For every edge \(e\) of the digraph \(G\), write \(\overline{e}\) for the edge \((t(e)', s(e)'')\) of the bipartite graph \(BP(G)\). Define a labeling \(\alpha\colon E \to \mathcal{M}\) by \[\alpha(e): = \{N \in \mathcal{M} : \overline{e} \in N\}.\] It is easy to verify that \(\alpha\) is a road coloring of \(G\).
Let \(\mathop{\mathrm{\mathrsfs{A}}}: = \mathop{\mathrm{\mathrsfs{A}}}(G,\alpha)\). Clearly, the letter \(M\) acts as a permutation so its defect is 0. By construction, for every edge \(f\in F\), the defect of the letter \(M_f\) is \(2\). Hence, the DFA \(\mathop{\mathrm{\mathrsfs{A}}}\) has no letter with defect 1, and therefore, none of the \((|V|-1)\)-element subsets is reachable in \(\mathop{\mathrm{\mathrsfs{A}}}\). Thus, the digraph \(G\) has a road coloring which is not completely reachable, a contradiction.
Now let \(w\) be the only vertex of \(G\) with more than one out-neighbor. We start a path from \(w\), going first to an out-neighbor \(w_1\) of \(w\) different from \(w\), then to the unique out-neighbor of \(w_1\), and so on. Since the digraph \(G\) is strongly connected, the path will return to \(w\) only after passing through all vertices of \(V\setminus\{w\}\). Since each of these vertices has only one out-neighbor, it occurs in the path exactly once whence the path is actually a Hamiltonian cycle in \(G\). ◻
Let \((\mathop{\mathrm{\mathbb{Z}}}_n, \oplus)\) denote the additive group of integers modulo \(n\). For each nonempty subset \(S\) of \(\mathop{\mathrm{\mathbb{Z}}}_n\), define \(W(S,n)\) to be the digraph \(\bigl(\mathop{\mathrm{\mathbb{Z}}}_n, \{(i,i\oplus 1) : i \in \mathop{\mathrm{\mathbb{Z}}}_n\} \cup \{(n-1, s) : s \in S\}\bigr)\). The digraphs \(W(S,n)\) may be viewed as generalizations of the well-known Wielandt digraph \(W_n\), which is precisely \(W(\{1\},n)\); see Fig. 7.
It turns out that digraphs all of whose colorings are completely reachable are in a sense equivalent to members of the family \(W(S,n)\).
For a digraph \(G=(V,E,s,t)\), its simplification is the digraph \(\bigl(V,E/{\sim},\bar s,\bar t\bigr)\), where \(\sim\) is an equivalence on \(E\) defined by \[e\sim f \quad\Longleftrightarrow\quad s(e)=s(f)\;\text{and}\;t(e)=t(f).\] and \(\bar s([e]):=s(e)\), \(\bar t([e])=t(e)\) for every equivalence class \([e]\in E/{\sim}\).
Theorem 3. All colorings of a digraph \(G\) with \(n\) vertices are completely reachable if and only if the simplification of \(G\) is isomorphic to the digraph \(W(S,n)\) for a subset \(S\subseteq\mathop{\mathrm{\mathbb{Z}}}_n\) that generates the group \((\mathop{\mathrm{\mathbb{Z}}}_n, \oplus)\).
Proof. Necessity. Lemma 3 clearly implies that the simplification of the digraph \(G\) is isomorphic to the digraph \(W(S,n)\) for some subset \(S\) of \(\mathop{\mathrm{\mathbb{Z}}}_n\). If the set \(S\) generates a proper subgroup of the group \((\mathop{\mathrm{\mathbb{Z}}}_n, \oplus)\), the greatest common divisor \(d\) of the set \(S\cup \{n\}\) is greater than 1. In this case, it is easy to see that \(d\) divides the length of every cycle in \(W(S,n)\) so that the period of \(W(S,n)\) is not equal to 1, that is, \(W(S,n)\) is not an aperiodic digraph. Then no completely reachable coloring of \(W(S,n)\) exists by Theorem 1. Hence, \(S\) must generate the entire group \((\mathop{\mathrm{\mathbb{Z}}}_n, \oplus)\).
Sufficiency. Complete reachability of every coloring of digraphs of the form \(W(S,n)\) with the set \(S\) generating the group \((\mathop{\mathrm{\mathbb{Z}}}_n, \oplus)\) readily follows from [2]. ◻
Clearly, the simplification \(G_{\mathrm{simp}}\) of a digraph \(G=(V,E,s,t)\) can be constructed in \(O(|E|)\) time. Checking whether \(G_{\mathrm{simp}}\) is isomorphic to a digraph \(W(S,|V|)\) amounts to verifying that \(G_{\mathrm{simp}}\) is strongly connected and has a unique vertex of out-degree greater than \(1\), which can be done in \(O(|V|+|E|)\) time. Finally, the subset \(S\subseteq \mathop{\mathrm{\mathbb{Z}}}_{|V|}\) generates the group \((\mathop{\mathrm{\mathbb{Z}}}_{|V|}, \oplus)\) if and only if the greatest common divisor of the set \(S\cup\{|V|\}\) is \(1\), and this can be checked in \(O(|V|)\) time using the Euclidean algorithm. Altogether, we see that Theorem 3 yields an algorithm that determines whether all colorings of a given digraph \((V,E,s,t)\) are completely reachable in \(O(|V|+|E|)\) time.
For comparison, we mention a result announced by D’Angeli and Rodaro at the Conference on Theoretical and Computational Algebra, held in Guimarães, Portugal, in June–July 2026, according to which the problem of determining whether all colorings of a given digraph are synchronizing is co-NP-complete.
urlstyle