Advertisement
Published in:
2012 | OriginalPaper | Chapter
P–NP Threshold for Synchronizing Road Coloring
Author : Adam Roman
Published in: Language and Automata Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The parameterized Synchronizing-Road-Coloring Problem (in short: SRCP
$_C^\ell$
) 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
$\{SRCP_C^\ell\}_{C,\ell}$
of problems parameterized with constants
C
and ℓ and try to find for which
C
and ℓ SRCP
$_C^\ell$
is
NP
-complete. It is known that SRCP
$_C^3$
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 SRCP
$_C^\ell$
is in
P
for
C
≤ 2 and ℓ ≥ 1. Hence, we solve SRCP almost completely for alphabet with 3 or more letters. The case
C
= 3 is still an open problem.