Decision Version of the Road Coloring Problem is NP-complete
Adam Roman
Abstract
After Trahtman in his brilliant paper solved the Road Coloring Problem,
a couple of new problems have arisen in the field of synchronizing
automata. Some of them naturally extends questions related to the
'classical' version of synchronization. Particulary, it is known that
the problem of finding the synchronizing word of a given length for a
given automaton is NP-complete. Volkov asked, what is the complexity of
the following problem: given a constant out-degree digraph (possibly
with multiple edges) and a natural number m, does there exist a
synchronizing word of length m for some synchronizing labeling of G. In
this paper we show that this decision version of the Road Coloring
Problem is NP-complete.