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

Независимым множеством в неориентированном графе G = (V, E) называется множество вершин, порождающее подграф, не содержащий дуг. Обозначим размер максимального независимого множества графа G как <math>\alpha (G) \; </math>. Для целого числа k, k-раскраска графа G представляет собой функцию V ! [1: : : k], которая назначает цвета вершинам G. Допустимой k-раскраской графа G является раскраска, в которой каждый цветовой класс представляет собой независимое множество. Наименьшее значение k, для которого существует допустимая k-раскраска графа G, называется хроматическим числом графа и обозначается /(G). Нахождение /(G) представляет собой фундаментальную NP-полную задачу. В силу этого, если ограничиваться алгоритмами с полиномиальным временем исполнения, мы переходим к вопросу об оценке значения /(G) или к тесно связанной с ним задаче приближенной раскраски графа.

Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации r = O f"('°g'°g")2') [12]. Это верно также для аппроксимации <math>\alpha (G) \; </math> [8]. Эти результаты могут показаться довольно слабыми, однако задача аппроксимации <math>\alpha (G) \; </math> и /(G) с коэффициентом nl~e для любой константы " > 0 является NP-полной [9, 14, 21]. Если использовать более строгие соображения о сложности, существует константа 0 < 8 < 1, такая, что ни одна задача не может быть аппроксимирована с коэффициентом и/21о« " [17, 21]. Рассмотрим задачу раскраски графа G при малом значении X(G). Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить.

Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых ~%{G) является неудачной оценкой /(G)? Можно ожидать, что ответ будет положительным, поскольку оценка /(G) за пределами коэффициента n1~s является сложной задачей. Так оно и оказывается на деле (даже если ~~$(G) мало). Некоторые из полученных результатов выражены в терминах максимального независимого множества <math>\alpha (G) \; </math> графа G. Поскольку /(G) > nla{G), эти результаты налагают нижнюю границу на /(G). Теорема 1 (i) утверждает, что выполненный в [15] изначальный анализ является строгим. Теорема 1 (ii) приводит границы для случая ~~$(G) = 3. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между /(G) и релаксациями l(G) и !2(G).

Теорема 7 ([10]) (i). Для всех константных значений " > 0 и k > 2 существует бесконечное число графов G, таких, что ~f(G) = k и a{G) < и /Л1"2^ (здесь A > ns для некоторых положительных константных значений). (ii) Существует бесконечное число графов G, таких, что ~x(G) = 3 и <math>\alpha (G) \; </math> < n0:843. (iii) Для некоторого константного значения c существует бесконечное число графов G, таких, что ~~$(G) = O(log n/loglogn) и <math>\alpha (G) \; </math> < logc n.

Векторная раскраска, включая 9-функцию Ловаса и ее варианты, также активно изучалась в контексте алгоритмов аппроксимации и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов.