The parameterized Synchronizing-Road-Coloring Problem (in short: SRCP_C~ℓ) in its decision version can be formulated as follows: given a digraph G with constant out-degree e, check if G can be synchronized by some word of length C for some synchronizing labeling. We consider the family {SRCP_C~ℓ)C,e of problems parameterized with constants C and e and try to find for which C and e SRCP_C~ℓ is NP-complete. It is known that SRCPJ? is NP-complete for C ≥ 8. We improve this result by showing that it is so for C > 4 and for t ≥ 3. We also show that SRCP_C~ℓ is in P for C ≤ 2 and e ≥ 1. Hence, we solve SRCP almost completely for alphabet with 3 or more letters. The case C = 3 is still an open problem.
展开▼
机译：决策版本中参数化的“同步道路着色”问题（简称：SRCP_C〜ℓ）可以表示如下：给定具有恒定出度e的有向图G，检查G是否可以与长度为C的某个单词同步一些同步标签。我们考虑用常数C和e参数化的问题的族（SRCP_C〜ℓ）C，e，并尝试找出SRCP_C〜ℓ的哪个C和e是NP完全的。众所周知，SRCPJ？在C≥8时是NP完全的。我们通过证明在C> 4且t≥3时是NP-完全的，我们还改善了这个结果。对于C≤2和e≥1，我们还表明SRCP_C〜_在P中。对于包含3个或更多字母的字母，我们几乎完全解决了SRCP问题。 C = 3的情况仍然是一个未解决的问题。
展开▼
