О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат

Сильносвязный орграф называется допустимым, если исходящие степени всех вершин в нём одинаковы и длины циклов взаимно просты в совокупности. Раскраской допустимого графа $G$ назовем произвольный автомат $A$, граф которого совпадает с $G$. Слово называется синхронизирующим автомат $A$, если оно переводит его в одно и то же состояние вне зависимости от исходного состояния автомата $A$. Оптимальная раскраска допустимого графа – это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок. Длину соответствующего синхронизирующего слова назовем значением оптимальной раскраски. Доказано, что любой приближенный полиномиальный алгоритм для вычисления оптимальной раскраски или ее значения имеет относительную погрешность не меньше 2 в случае трехбуквенного алфавита при предположении $\mathcal P\neq\mathcal{NP}$. Также показано, как результат можно перенести на случай двухбуквенного алфавита.