A note on polynomial approximation of synchronizing optimal coloring | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 2(12).

A strongly connected aperiodic directedgraph with constant out-degree is called admissible. An automaton A is a coloring of admissiblegraph G if the underlying graph of A equals G. A word is called synchronizingfor an automaton A if it takes A to a one particular state no matter of the starting state.Optimal coloring of admissible graph G is a synchronizing coloring with shortest reset wordamong all synchronizing colorings of G. The length of the corresponding reset word is calledoptimal coloring value. We prove that unless P = N P , no polynomial-time algorithm approximatesoptimal coloring or optimal coloring value within a factor less than 2 in the3-letter alphabet case. We also extend this result to the 2-letter alphabet case.