Abstract
By the Road Coloring Theorem (Trahtman, 2008), the edges of any given aperiodic strongly connected directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted.
In this paper we consider the following problem: given a word w and digraph G, is it true that G has a coloring that is synchronized by w? We show that it is NP-complete for certain fixed words. For the binary alphabet we present a classification that separates such words from those that make the problem solvable in polynomial time.
The classification differs if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete.