Точный алгоритм раскраски графа с использованием метода включения-исключения
Ключевые слова и синонимы
Постановка задачи
Алгоритм k-раскраски графа G = (V, E) присваивает один из k цветов каждой вершине графа таким образом, чтобы соседние вершины имели разные цвета. Также используется название «раскраска вершин».
Наименьшее целочисленное значение k, для которого существует k-раскраска графа G, называется хроматическим числом графа и обозначается [math]\displaystyle{ \chi(G) \; }[/math]. Число k-раскрасок графа G, обозначаемое P(G;k), называется хроматическим многочленом.
Основные результаты
Отмечено, что [math]\displaystyle{ \chi(G) \; }[/math] и P(G;k) могут быть выражены при помощи формулы включения-исключения, члены которой определяются набором независимых множеств порожденных подграфов G. Пусть [math]\displaystyle{ X \subseteq V \; }[/math] и пусть [math]\displaystyle{ s(X) \; }[/math] – число непустых независимых подмножеств вершин, не пересекающихся с X; пусть [math]\displaystyle{ s_r(X) \; }[/math] обозначает число способов выбора r непустых независимых подмножеств [math]\displaystyle{ S_1, ..., S_r \; }[/math] (возможно, перекрывающихся с повторениями), не пересекающихся с X, таких, что [math]\displaystyle{ |S_1| + ... + |S_r| = |V| \; }[/math].
Теорема 1. Пусть G – граф с n вершинами.
1. [math]\displaystyle{ \chi(G) = min_{k \in \{1, ..., n\}} \bigg\{k: \sum_{X \subseteq V} (-1)^{|X|} s(X)^k \gt 0 \bigg\} \; }[/math]
2. Для k = 1, ..., k
[math]\displaystyle{ P(G;k) = \sum_{r=1}^k \binom{k}{r} \bigg(\sum_{X \subseteq V} (-1)^{|X|} s_r(X) \bigg) }[/math], (k = 1, 2, ..., n).
Время, необходимое для оценки этих выражений, зависит от [math]\displaystyle{ 2^n \; }[/math] оценок [math]\displaystyle{ s(X) \; }[/math] и [math]\displaystyle{ s_r(X) \; }[/math], соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений соответствуют [math]\displaystyle{ 2^n \; }[/math] с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению
[math]\displaystyle{ s(X) = \begin{cases} 0, & если X = V \\ s \Big(X \cup \{ v \} \Big) + s\Big(X \cup \{ v \} \cup N(v)\Big) + 1, & v \not\in X\ \end{cases} }[/math]
где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем выполнения и полиномиальным объемом памяти, описанных в литературе.
Это дает нам следующие границы:
Теорема 2. Для графа G с n вершинами значения [math]\displaystyle{ \chi(G) \; }[/math] и [math]\displaystyle{ P(G; k) \; }[/math] могут быть вычислены со следующими затратами ресурсов:
1. время и объем памяти [math]\displaystyle{ 2^n n^{O(1)} \; }[/math];
2. время [math]\displaystyle{ O(2.2461^n) \; }[/math] и полиномиальный объем памяти.
Оптимальную раскраску, дающую [math]\displaystyle{ \chi(G) \; }[/math], можно найти с теми же затратами времени и объема памяти.
Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера n, при условии, что членство в семействе можно определить за полиномиальное время.
Применение
Раскраска графа – не только фундаментальная проблема комбинаторной оптимизации; она возникает в множестве приложений, включая распределение регистров и составление графиков.
Литература
1. Bjorklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. In: Proc. 33rd ICALP. LNCS, vol. 4051, pp. 548-1559. Springer (2006). Algorithmica, doi: 10.1007/s00453-007-9149-8
2. Bjorklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput.
3. Bjorklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Mobius: fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, June 11-13, 2007. Association for Computing Machinery, pp. 67-74. New York (2007)
