4430
правок
Раскраска графа: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 39 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Кликовое покрытие | Кликовое покрытие | ||
== Постановка задачи == | == Постановка задачи == | ||
Независимым множеством в неориентированном графе 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-полную задачу. В силу этого, если ограничиваться алгоритмами с полиномиальным временем | Независимым множеством в неориентированном графе 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> или к тесно связанной с ним задаче приближенной раскраски графа. | ||
Задача 1 (приближенная раскраска) | '''Задача 1 (приближенная раскраска)''' | ||
Дано: неориентированный граф G = (V, E). | Дано: неориентированный граф G = (V, E). | ||
Требуется: | Требуется: выдать допустимую раскраску графа G при помощи <math> r \cdot \chi (G) \; </math> цветов для некоторого коэффициента аппроксимации <math>r \ge 1 \; </math>. | ||
Задача: минимизация r. | Задача: минимизация r. | ||
Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации r = O | Пусть 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>. Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить. | ||
== Векторная раскраска графов == | == Векторная раскраска графов == | ||
Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении | Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении <math>\chi (G) \; </math> [1, 3, 13, 15], основываются на идее [[векторная раскраска графа|векторной раскраски]], предложенной Карджером, Мотвани и Суданом [15]. | ||
(Векторная раскраска, предложенная в [15], тесно связана с <math>\theta</math>-функцией Ловаса [19]. Эта связь будет обсуждаться ниже). | |||
Определение 1. Векторная k-раскраска графа заключается в присваивании вершинам графа единичных векторов, таких, что для каждой дуги скалярное произведение векторов, присвоенных ее конечным точкам, не превышает (в том смысле, что оно может только быть более отрицательным). | '''Определение 1.''' Векторная k-раскраска графа заключается в присваивании вершинам графа единичных векторов, таких, что для каждой дуги скалярное произведение векторов, присвоенных ее конечным точкам, не превышает -1/(k - 1) (в том смысле, что оно может только быть более отрицательным). | ||
Наименьшее значение k, для которого существует векторная k-раскраска графа G, называется векторным хроматическим числом графа и обозначается | Наименьшее значение k, для которого существует векторная k-раскраска графа G, называется векторным хроматическим числом графа и обозначается <math>\overrightarrow{\chi} (G)</math>. Векторное хроматическое число можно охарактеризовать следующим образом: | ||
<math>\overrightarrow{\chi} (G)</math> Минимизировать k | |||
Здесь мы предполагаем, что V = [1... n] и что векторы | при условии: <math>\langle v_i, v_j \rangle \le - \frac {1} {k - 1} \; \; \forall (i, j) \in E</math> | ||
<math>\langle v_i, v_i \rangle = 1 \; \; \forall i \in V</math>. | |||
Здесь мы предполагаем, что V = [1... n] и что векторы <math>\{ v_i \}_{i=1}^n </math> принадлежат к <math>R_n \; </math>. Каждый k-раскрашиваемый граф также является векторно k-раскрашиваемым. Это можно показать, если идентифицировать каждый цветовой класс с одной вершиной идеального (k-1)-мерного симплекса с центром в источнике. Более того, в отличие от хроматического числа, векторная k-раскраска, если таковая существует, может быть найдена за полиномиальное время при помощи алгоритмов полуопределенного программирования (с поправкой на произвольно малую ошибку в скалярных произведениях). | |||
'''Утверждение 1 (сложность векторной раскраски [15])'''. Пусть <math>\varepsilon > 0 \; </math>. Если граф G имеет векторную k-раскраску, то векторная <math>(k + \varepsilon) \;</math> -раскраска графа G может быть построена за время, полиномиальное относительно <math>n \; </math> и <math>log(1 / \varepsilon) \; </math>. | |||
Можно усилить определение 1, чтобы получить другое понятие векторной раскраски и векторного хроматического числа. | Можно усилить определение 1, чтобы получить другое понятие векторной раскраски и векторного хроматического числа. | ||
при условии: | <math>\overrightarrow{\chi}_2 (G)</math> Минимизировать k | ||
1 | |||
при условии: <math>\langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E</math> | |||
<math>\langle v_i, v_i \rangle = 1 \; \; \forall i \in V</math>. | |||
1 | |||
i | |||
<math>\overrightarrow{\chi}_3 (G)</math> Минимизировать k | |||
при условии: <math>\langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E</math> | |||
<math>\langle v_i, v_j \rangle \ge - \frac {1} {k - 1} \; \; \forall i, j \in V</math> | |||
<math>\langle v_i, v_i \rangle = 1 \; \; \forall i \in V</math>. | |||
Функция <math>\overrightarrow{\chi}_2 (G)</math>, вычисляющая '''точное''' векторное хроматическое число графа G, равна <math>\theta</math>-функции Ловаса на <math>\bar{G}</math> [15, 19], где <math>\bar{G}</math> – дополнение графа G. Функция <math>\overrightarrow{\chi}_3 (G)</math> называется '''сильным''' векторным хроматическим числом. Аналог утверждения 1 верен как для <math>\overrightarrow{\chi}_2 (G)</math>, так и для <math>\overrightarrow{\chi}_3 (G)</math>. Обозначим размер максимальной клики графа G как <math>\omega (G) \; </math>; тогда имеет место соотношение <math>\omega(G) \le \overrightarrow{\chi} (G) \le \overrightarrow{\chi}_2 (G) \le \overrightarrow{\chi}_3 (G) \le \chi (G) \; </math>. | |||
== Основные результаты == | == Основные результаты == | ||
Предположим, что граф G имеет n вершин и максимальную степень | Предположим, что граф G имеет <math>n \; </math> вершин и максимальную степень <math>\Delta \; </math>. Нотации <math>\tilde{O} (\cdot) \; </math> и <math>\tilde{\Omega} (\cdot) \; </math> используются для подавления полилогарифмических множителей. Основной результат Карджера, Мотвани и Судана [15] заключается в следующем: | ||
Теорема 1 ([15]) Если | '''Теорема 1 ([15]) Если <math>\overrightarrow{\chi} (G) = k \;</math> , то граф G может быть раскрашен за полиномиальное время при помощи <math>min \{ \tilde{O}(\Delta^{1-2/k}), \tilde{O}(n^{1-3/(k+1)}) \}</math> цветов.''' | ||
Как упоминалось выше, использование векторной раскраски в контексте приближенной раскраски было впервые предложено в работе [15]. Грубо говоря, при наличии векторной раскраски графа G алгоритм, предложенный в [15], находит большое независимое множество в G. Это независимое множество соответствует множеству векторов в векторной раскраске, находящихся близко друг другу (и следовательно, по определению, не имеющих общей дуги). Сочетание этого подхода с идеями Вигдерсона [20] доказывает справедливость теоремы 1. | Как упоминалось выше, использование векторной раскраски в контексте приближенной раскраски было впервые предложено в работе [15]. Грубо говоря, при наличии векторной раскраски графа G алгоритм, предложенный в [15], находит большое независимое множество в G. Это независимое множество соответствует множеству векторов в векторной раскраске, находящихся близко друг к другу (и следовательно, по определению, не имеющих общей дуги). Сочетание этого подхода с идеями Вигдерсона [20] доказывает справедливость теоремы 1. | ||
Ниже приводится описание родственных работ. Первые две из нижеследующих теорем появились еще до выхода работы Карджера, Мотвани и Судана [15]. | Ниже приводится описание родственных работ. Первые две из нижеследующих теорем появились еще до выхода работы Карджера, Мотвани и Судана [15]. | ||
Теорема 2 ([20]). Если | '''Теорема 2 ([20]). Если <math>\chi (G) = k \;</math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>O(k n^{1-1/(k-1)}) \; </math> цветов.''' | ||
Теорема 3 ([2]). Если | '''Теорема 3 ([2]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/8}) \; </math> цветов. Если <math>\chi (G) \; = k \ge 4 </math>, то граф G может быть раскрашен за полиномиальное время при помощи не более чем <math>\tilde{O} (n^{1-1/(k-3/2)}) \; </math> цветов.''' | ||
Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с | Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с <math>\chi (G) = 3, 4 \; </math> (эти результаты также были расширены для более высоких значений <math>\chi (G) \; </math>). | ||
Теорема 4 ([3]). Если | '''Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/14}) \; </math> цветов.''' | ||
Теорема 5 ([13]). Если | '''Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/19}) \; </math> цветов.''' | ||
Наилучший известный на данный момент результат для раскраски графа в три цвета приведен в [1]. Описанный в этой работе алгоритм использует релаксацию алгоритма строгой векторной раскраски (т.е. | Наилучший известный на данный момент результат для раскраски графа в три цвета приведен в [1]. Описанный в этой работе алгоритм использует релаксацию алгоритма строгой векторной раскраски (т.е. <math>\overrightarrow{\chi}_2 \; </math>), дополненную определенными ограничениями для нечетных циклов. | ||
Теорема 6 ([1]). Если | '''Теорема 6 ([1]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>O(n^{0.2111}) \; </math> цветов.''' | ||
Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) k( | Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) <math>k^{(log \; k)/25}</math> цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски. | ||
Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых <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> существует бесконечное число графов G, таких, что <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) Существует бесконечное число графов G, таких, что <math>\overrightarrow{\chi} (G) = 3 \; </math> и <math>\alpha (G) \le n^{0.843} \; </math>. (iii) Для некоторого константного значения <math>c \; </math> существует бесконечное число графов G, таких, что <math>\overrightarrow{\chi} (G) = O(log \; n/log \; log \; n) \; </math> и <math>\alpha (G) \le log^c n \; </math>.''' | |||
'''Теорема 8 ([7]). Для некоторого константного значения <math>c \; </math> существует бесконечное число графов G, таких, что <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>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов. | |||
== Применение == | == Применение == | ||
Помимо своей теоретической значимости, раскраска графов имеет несколько конкретных практических применений в области моделирования бесконфликтного распределения ресурсов (например, [4, 5]). | Помимо своей теоретической значимости, раскраска графов имеет несколько конкретных практических применений в области моделирования бесконфликтного распределения ресурсов (например, [4, 5]). | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением | Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как можно также рассматривать более сильные релаксации – такие как <math>\overrightarrow{\chi}_2 (G) \; </math> и <math>\overrightarrow{\chi}_3 (G) \; </math>. Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций. | ||
== См. также == | == См. также == | ||
* ''[[Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях]] | |||
* ''[[Максимальный разрез]] | |||
* ''[[Рандомизированное округление]] | |||
* ''[[Самый разреженный разрез]] | |||
== Литература == | == Литература == | ||
| Строка 146: | Строка 148: | ||
13. Halperin, E., Nathaniel, R., Zwick, U.: Coloring k-colorable graphs using smaller palettes. J. Algorithms 45, 72-90 (2002) | 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 | 14. Hastad, J.: Clique is hard to approximate within <math>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) | 15. Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45(2), 246-265 (1998) | ||
