Точный алгоритм раскраски графа с использованием метода включения-исключения
Ключевые слова и синонимы
Постановка задачи
Алгоритм k-раскраски графа G = (V, E) присваивает один из k цветов каждой вершине графа таким образом, чтобы соседние вершины имели разные цвета. Также используется название «раскраска вершин».
Наименьшее целочисленное значение k, для которого существует k-раскраска графа G, называется хроматическим числом графа и обозначается /(G). Число k-раскрасок графа G, обозначаемое P(G, k), называется хроматическим многочленом.
Основные результаты
Отмечено, что /(G) и P(G, k) могут быть выражены при помощи формулы включения-исключения, члены которой определяются набором независимых множеств порожденных подграфов G. Пусть X С V и пусть s(X) – число непустых независимых подмножеств вершин, не пересекающихся с X; пусть sr(X) обозначает число способов выбора r непустых независимых подмножеств S1…, …, Sr (возможно, перекрывающихся с повторениями), не пересекающихся с X, таких, что jS1j + ---+ jSrj = jVj.
Теорема 1. Пусть G – граф с n вершинами. 1.
X(G)= min nk: X (-l)lxls(X)k > 0 o :
- 6{i,..,»> * £v >
к
к
к
к
2. Fork = 1;::: ;k,
P(G; k) =
E^
r=1 r XQV
(k = 1,2,...,и).
Время, необходимое для оценки этих выражений, зависит от 2n оценок s(X) и sr(X), соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений определяются 2n с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению s(X) = 0; ifX=V; s(x U {v}) + s(x [ fvg [ N(v)\ + 1; for v £ X ; где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе.
Это дает нам следующие границы:
Теорема 2. Для графа G с n вершинами значения x(G) и P(G, k) могут быть вычислены со следующими результатами:
1. время и объем памяти 2n nO(1);
2. время O(2:2461n) и полиномиальный объем памяти.
Оптимальную раскраску, дающую /(G), можно найти с теми же затратами времени и объема памяти.
Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера 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)