The NP-completeness of the Road Coloring Problem

Research highlights
► We present 3 different decision problems related to finite automata synchronization and the corresponding versions of these problems for the Road Coloring Problem.
► We prove the NP-completeness of one of this versions, namely: “given a constant out-degree graph G and a natural number m, check if G can be synchronized by some word of length m for some synchronizing labeling”.
► We also prove a much stronger result: if m in the above problem is constant, the problem remains NP-complete.