Completely Reachable Road Coloring

Abstract

We characterize the digraphs that admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. This class of digraphs can be recognized in polynomial time. In contrast, we show that, for every fixed alphabet size, the problem of deciding whether a digraph admits an edge labeling with the same property is NP-complete. We also classify the digraphs for which every edge labeling results in a completely reachable automaton.

arXiv comment15 pages, 6 figures. In version 4, a gap in the proof of Lemma 5 has been filled