Раскраска графа

Ключевые слова и синонимы

Кликовое покрытие

Постановка задачи

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

Задача 1 (приближенная раскраска)

Дано: неориентированный граф G = (V, E).

Требуется: выдать допустимую раскраску графа G при помощи [math]\displaystyle{ r \cdot \chi (G) \; }[/math] цветов для некоторого коэффициента аппроксимации [math]\displaystyle{ r \ge 1 \; }[/math].

Задача: минимизация r.

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

Векторная раскраска графов

Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении [math]\displaystyle{ \chi (G) \; }[/math] [1, 3, 13, 15], основываются на идее векторной раскраски, предложенной Карджером, Мотвани и Суданом [15]. (Векторная раскраска, предложенная в [15], тесно связана с [math]\displaystyle{ \theta }[/math]-функцией Ловаса [19]. Эта связь будет обсуждаться ниже).

Определение 1. Векторная k-раскраска графа заключается в присваивании вершинам графа единичных векторов, таких, что для каждой дуги скалярное произведение векторов, присвоенных ее конечным точкам, не превышает -1/(k - 1) (в том смысле, что оно может только быть более отрицательным).

Наименьшее значение k, для которого существует векторная k-раскраска графа G, называется векторным хроматическим числом графа и обозначается [math]\displaystyle{ \overrightarrow{\chi} (G) }[/math]. Векторное хроматическое число можно охарактеризовать следующим образом:

[math]\displaystyle{ \overrightarrow{\chi} (G) }[/math] Минимизировать k

при условии: [math]\displaystyle{ \langle v_i, v_j \rangle \le - \frac {1} {k - 1} \; \; \forall (i, j) \in E }[/math]

[math]\displaystyle{ \langle v_i, v_i \rangle = 1 \; \; \forall i \in V }[/math].

Здесь мы предполагаем, что V = [1... n] и что векторы [math]\displaystyle{ \{ v_i \}_{i=1}^n }[/math] принадлежат к [math]\displaystyle{ R_n \; }[/math]. Каждый k-раскрашиваемый граф также является векторно k-раскрашиваемым. Это можно показать, если идентифицировать каждый цветовой класс с одной вершиной идеального (k-1)-мерного симплекса с центром в источнике. Более того, в отличие от хроматического числа, векторная k-раскраска, если таковая существует, может быть найдена за полиномиальное время при помощи алгоритмов полуопределенного программирования (с поправкой на произвольно малую ошибку в скалярных произведениях).

Утверждение 1 (сложность векторной раскраски [15]). Пусть [math]\displaystyle{ \varepsilon \gt 0 \; }[/math]. Если граф G имеет векторную k-раскраску, то векторная [math]\displaystyle{ (k + \varepsilon) \; }[/math] -раскраска графа G может быть построена за время, полиномиальное относительно [math]\displaystyle{ n \; }[/math] и [math]\displaystyle{ log(1 / \varepsilon) \; }[/math].

Можно усилить определение 1, чтобы получить другое понятие векторной раскраски и векторного хроматического числа.

[math]\displaystyle{ \overrightarrow{\chi}_2 (G) }[/math] Минимизировать k

при условии: [math]\displaystyle{ \langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E }[/math]

[math]\displaystyle{ \langle v_i, v_i \rangle = 1 \; \; \forall i \in V }[/math].

[math]\displaystyle{ \overrightarrow{\chi}_3 (G) }[/math] Минимизировать k

при условии: [math]\displaystyle{ \langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E }[/math]

[math]\displaystyle{ \langle v_i, v_j \rangle \ge - \frac {1} {k - 1} \; \; \forall i, j \in V }[/math]

[math]\displaystyle{ \langle v_i, v_i \rangle = 1 \; \; \forall i \in V }[/math].

Функция [math]\displaystyle{ \overrightarrow{\chi}_2 (G) }[/math], вычисляющая точное векторное хроматическое число графа G, равна [math]\displaystyle{ \theta }[/math]-функции Ловаса на [math]\displaystyle{ \bar{G} }[/math] [15, 19], где [math]\displaystyle{ \bar{G} }[/math] – дополнение графа G. Функция [math]\displaystyle{ \overrightarrow{\chi}_3 (G) }[/math] называется сильным векторным хроматическим числом. Аналог утверждения 1 верен как для [math]\displaystyle{ \overrightarrow{\chi}_2 (G) }[/math], так и для [math]\displaystyle{ \overrightarrow{\chi}_3 (G) }[/math]. Обозначим размер максимальной клики графа G как [math]\displaystyle{ \omega (G) \; }[/math]; тогда имеет место соотношение [math]\displaystyle{ \omega(G) \le \overrightarrow{\chi} (G) \le \overrightarrow{\chi}_2 (G) \le \overrightarrow{\chi}_3 (G) \le \chi (G) \; }[/math].

Основные результаты

Предположим, что граф G имеет [math]\displaystyle{ n \; }[/math] вершин и максимальную степень [math]\displaystyle{ \Delta \; }[/math]. Нотации [math]\displaystyle{ \tilde{O} (\cdot) \; }[/math] и [math]\displaystyle{ \tilde{\Omega} (\cdot) \; }[/math] используются для подавления полилогарифмических множителей. Основной результат Карджера, Мотвани и Судана [15] заключается в следующем:

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

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

Ниже приводится описание родственных работ. Первые две из нижеследующих теорем появились еще до выхода работы Карджера, Мотвани и Судана [15].

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

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

Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с [math]\displaystyle{ \chi (G) = 3, 4 \; }[/math] (эти результаты также были расширены для более высоких значений [math]\displaystyle{ \chi (G) \; }[/math]).

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

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

Наилучший известный на данный момент результат для раскраски графа в три цвета приведен в [1]. Описанный в этой работе алгоритм использует релаксацию алгоритма строгой векторной раскраски (т.е. [math]\displaystyle{ \overrightarrow{\chi}_2 \; }[/math]), дополненную определенными ограничениями для нечетных циклов.

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

Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) [math]\displaystyle{ k^{(log \; k)/25} }[/math] цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски.

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

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

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

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

Применение

Помимо своей теоретической значимости, раскраска графов имеет несколько конкретных практических применений в области моделирования бесконфликтного распределения ресурсов (например, [4, 5]).

Открытые вопросы

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

См. также

• Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях
• Максимальный разрез
• Рандомизированное округление
• Самый разреженный разрез

Литература

1. Arora, S., Chlamtac, E., Charikar, M.: New approximation guarantee for chromatic number. In: Proceedings of the 38th annual ACM Symposium on Theory of Computing (2006) pp. 215-224.

2. Blum, A.: New approximations for graph coloring. J. ACM 41 (3), 470-516(1994)

3. Blum, A., Karger, D.: An O(n3/14)-coloring for 3-colorable graphs. Inf. Process. Lett. 61 (6),49-53 (1997)

4. Chaitin, G.J.: Register allocation & spilling via graph coloring. In: Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction (1982) pp. 98-105.

5. Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Comp. Lang. 6,47-57 (1981)

6. Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. In: Proceedings of the 38th annual ACM Symposium on Theory of Computing (2006) pp. 344-353.

7. Feige, U.: Randomized graph products, chromatic numbers, and the Lovasz theta function. Combinatorica 17(1), 79-90 (1997)

8. Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219-225 (2004)

9. Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57,187-199 (1998)

10. Feige, U., Langberg, M., Schechtman, G.: Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J. Comput. 33(6), 1338-1368 (2004)

11. Guruswami, V., Khanna, S.: On the hardness of 4-coloring a 3-colorable graph. In: Proceedings of the 15th annual IEEE Conference on Computational Complexity (2000) pp. 188-197.

12. Halldorsson, M.: A still better performance guarantee for approximate graph coloring. Inf. Process. Lett. 45, 19-23 (1993)

13. Halperin, E., Nathaniel, R., Zwick, U.: Coloring k-colorable graphs using smaller palettes. J. Algorithms 45, 72-90 (2002)

14. Hastad, J.: Clique is hard to approximate within [math]\displaystyle{ n^{1 - \varepsilon} }[/math]. Acta Math. 182(1), 105-142 (1999)

15. Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45(2), 246-265 (1998)

16. Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica 20, 393-415 (2000)

17. Khot, S.: Improved inapproximability results for max clique, chromatic number and approximate graph coloring. In: Proceedings of the 42nd annual IEEE Symposium on Foundations of Computer Science (2001) pp. 600-609.

18. Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th annual ACM symposium on Theory of Computing (2002) pp. 767-775.

19. Lovasz, L.:On the Shannon capacity of a graph. IEEE Trans. Inf. Theor. 25, 2-13(1979)

20. Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J. ACM 30(4), 729-735 (1983)

21. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th annual ACM symposium on Theory of Computing (2006) pp. 681-690.