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/

[1] Adler R. L., Weiss B., Goodwyn L. W., “Equivalents of topological Markov shifts”, Isr. J. Math., 27:1 (1977), 49–63 | DOI | MR | Zbl

[2] Trahtman A. N., The Road Coloring Problem, 2007, arXiv: 0709.0099 | MR

[3] Volkov M., “Synchronizing Automata and the Cerny conjecture”, LNCS, 5196, 2008, 11–27 | MR | Zbl

[4] Černý J., “Poznámka k homogénnym eksperimentom s konečnými automatami”, Matematicko-fyzikalny Časopis Slovensk. Akad. Vied, 14:3 (1964), 208–216 (in Slovak) | MR | Zbl

[5] Adler R. L., Weiss B., “Similarity of automorphisms of the torus”, Mem. Amer. Math. Soc., 98 (1970), 1–43 | MR | Zbl

[6] Beal M., Perrin D., A quadratic algorithm for road coloring, 2008, arXiv: 0803.0726

[7] Eppstein D., “Reset sequences for monotonic automata”, SIAM J. Comput., 19 (1990), 500–510 | DOI | MR | Zbl

[8] Berlinkov M., “Approximating the Minimum Length of Synchronizing Words is Hard”, LNCS, 6072, 2010, 37–47 | Zbl

[9] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR