Completely Reachable Road Coloring
arXiv:2607.12078
The paper characterizes directed graphs that can be edge‑labeled by a finite alphabet to produce a completely reachable automaton, provides a polynomial‑time recognition algorithm, proves the problem becomes NP‑complete when the alphabet size is fixed, and classifies graphs where every labeling yields a completely reachable automaton.
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.
15 pages, 7 figures. In version 3, simple digraphs are discussed in Section 1