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

作者：Roman A^*; Drewienkowski M

来源：Information and Computation, 2015, 242: 383-393.

DOI：10.1016/j.ic.2015.04.004

• Road Coloring Problem
• Synchronizing word
• Cerny conjecture
• Synchronizing automata
• Reset word

The parameterized Synchronizing-Road-Coloring Problem (in short: SRCPCl) in its decision version can be formulated as follows: given a digraph Gwith constant out-degree l, check if G can be synchronized by some word of length C for some synchronizing labeling. We consider the family {SRCPCl}(C, l) of problems parameterized with constants C and l and try to find for which C and l the problem SRCPCl 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 >= 4and for l >= 3. We also show that SRCPCl is in P for C <= 2and l >= 1. Finally, we solve the problem completely for the non-binary alphabets by showing that SRCP3l is in P for l >= 3.

• 出版日期2015-6