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

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

<math>\langle v_i, v_j \rangle = 1 \; \; \forall i \in V</math>.

Как упоминалось выше, использование векторной раскраски в контексте приближенной раскраски было впервые предложено в работе [15]. Грубо говоря, при наличии векторной раскраски графа G алгоритм, предложенный в [15], находит большое независимое множество в G. Это независимое множество соответствует множеству векторов в векторной раскраске, находящихся близко друг другу (и следовательно, по определению, не имеющих общей дуги). Сочетание этого подхода с идеями Вигдерсона [20] доказывает справедливость теоремы 1.

'''Теорема 2 ([20]). Если <math>\chi (G) = k \;</math> , то граф G может быть раскрашен за полиномиальное время при помощи <math>O(k n^{1-1/(k-1)}) \; </math> цветов.'''

'''Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/9}) \; </math> цветов.'''

Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых <math>\overrightarrow{\chi} (G) \; </math> является неудачной оценкой <math>\chi (G) \; </math>? Можно ожидать, что ответ будет положительным, поскольку оценка <math>\chi (G) \; </math> за пределами коэффициента <math>n^{1 - \varepsilon} \; </math> является сложной задачей. Так оно и оказывается на деле (даже если <math>\overrightarrow{\chi} (G) \; </math> мало). Некоторые из полученных результатов выражены в терминах максимального независимого множества <math>\alpha (G) \; </math> графа G. Поскольку <math>\chi (G) \ge n / \alpha (G) \; </math>, эти результаты налагают нижнюю границу на <math>\chi (G) \; </math>. Теорема 1 (i) утверждает, что выполненный в [15] изначальный анализ является строгим. Теорема 1 (ii) приводит границы для случая <math>\overrightarrow{\chi} (G) = 3 \; </math>. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между <math>\chi (G) \; </math> и релаксациями <math>\overrightarrow{\chi} (G) \; </math> и <math>\overrightarrow{\chi}_2 (G) \; </math>.

'''Теорема 7 ([10]) (i). Для всех константных значений <math>\varepsilon > 0 \; </math> и <math>k > 2 \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = k \; </math> и <math>\alpha (G) \le n / \Delta^{1-2/k - \varepsilon}</math> (здесь <math>\Delta > n^{\delta} \; </math> для некоторой константы <math>\delta > 0 \; </math>). (ii) Существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = 3 \; </math> и <math>\alpha (G) \le n^{0.843} \; </math>. (iii) Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = O(log \; n/log \; log \; n) \; </math> и <math>\alpha (G) \le log^c n \; </math>.'''

'''Теорема 8 ([7]). Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi}_2 (G) \le 2 \sqrt{log \; n} \; </math> и <math>\chi (G) \ge n / 2^{c \sqrt{log \; n}} \; </math>  >'''

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

Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как стоит рассмотреть более сильные релаксации – такие как <math>\overrightarrow{\chi}_2 (G) \; </math> и <math>\overrightarrow{\chi}_3 (G) \; </math>. Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций.

► Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях

► Максимальный разрез

► Самый разреженный разрез