Geodesic
A note on polynomial approximation of synchronizing optimal coloring
Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 49-72

Voir la notice de l'article provenant de la source Math-Net.Ru

A strongly connected aperiodic directed graph with constant out-degree is called admissible. An automaton $A$ is a coloring of admissible graph $G$ if the underlying graph of $A$ equals $G$. A word is called synchronizing for an automaton $A$ if it takes $A$ to a one particular state no matter of the starting state. Optimal coloring of admissible graph $G$ is a synchronizing coloring with shortest reset word among all synchronizing colorings of $G$. The length of the corresponding reset word is called optimal coloring value. We prove that unless $\mathcal P=\mathcal{NP}$, no polynomial-time algorithm approximates optimal coloring or optimal coloring value within a factor less than 2 in the 3-letter alphabet case. We also extend this result to the 2-letter alphabet case.
Keywords: road coloring problem, optimal coloring, synchronizing automata. 
@article{PDM_2011_2_a3,
     author = {M. V. Berlinkov},
     title = {A note on polynomial approximation of synchronizing optimal coloring},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {49--72},
     publisher = {mathdoc},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_2_a3/}
}
TY  - JOUR
AU  - M. V. Berlinkov
TI  - A note on polynomial approximation of synchronizing optimal coloring
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 49
EP  - 72
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_2_a3/
LA  - ru
ID  - PDM_2011_2_a3
ER  - 
%0 Journal Article
%A M. V. Berlinkov
%T A note on polynomial approximation of synchronizing optimal coloring
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 49-72
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_2_a3/
%G ru
%F PDM_2011_2_a3
M. V. Berlinkov. A note on polynomial approximation of synchronizing optimal coloring. Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 49-72. http://geodesic.mathdoc.fr/item/PDM_2011_2_a3/