Раскраска графа: различия между версиями

Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации <math>r = O \Bigg( \frac{n ( log \; log \; n)^2}{log^3 \; n} \Bigg)</math> [12]. Это верно также для аппроксимации <math>\alpha (G) \; </math> [8]. Эти результаты могут показаться довольно слабыми, однако задача аппроксимации <math>\alpha (G) \; </math> и <math>\chi (G) \; </math> с коэффициентом <math>n^{l - \varepsilon} \; </math> для любой константы <math>\varepsilon > 0 \; </math> является NP-полной [9, 14, 21]. Если использовать более строгие соображения о сложности, существует константа <math>0 < \delta < 1 \; </math>, такая, что ни одна задача не может быть аппроксимирована с коэффициентом <math>n / 2^{log^{\delta} \; n}</math> [17, 21]. Рассмотрим задачу раскраски графа G при малом значении <math>\chi (G) \; </math>. Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить.