A complete solution to the complexity of Synchronizing Road Coloring for non-binary alphabets

The parameterized Synchronizing-Road-Coloring Problem (in short: SRCPCℓ) in its decision version can be formulated as follows: given a digraph G with constant out-degree ℓ, check if G can be synchronized by some word of length C for some synchronizing labeling. We consider the family {SRCPCℓ}C,ℓ of problems parameterized with constants C and ℓ and try to find for which C and ℓ the problem SRCPCℓ is NP-complete. It is known that SRCPC3 is NP-complete for C≥8. We improve this result by showing that it is so for C≥4 and for ℓ≥3. We also show that SRCPCℓ is in P for C≤2 and ℓ≥1. Finally, we solve the problem completely for the non-binary alphabets by showing that SRCP3ℓ is in P for ℓ≥3.