Цветовое кодирование: различия между версиями

Цветной путь длины k - 1, начинающийся в некоторой конкретной вершине s, вычисляется при помощи методов динамического программирования. Предположим, что для каждой вершины <math>v \in V</math> задано множество возможных цветов для цветных путей длины i, соединяющих s и v. Заметим, что нет необходимости записывать все цветные пути, соединяющие s и v. Вместо этого запишем все множества цветов, появляющихся на этих путях. Для каждой вершины v существует набор из не более чем <math>\binom{k}{i}</math> множеств цветов. Теперь проверим каждое подмножество C, принадлежащее к набору v, и каждое ребро <math>(v, u) \in E</math>. Если <math>c(u) \notin C</math>, добавим множество <math>C \cup \{ c(u) \}</math> к набору u, соответствующему цветным путям длины i + 1. Граф G содержит цветной путь длины k - 1 с раскраской ''c'' в том и только том случае, если окончательная коллекция, соответствующая путям длины k - 1, непуста по крайней мере для одной вершины. Количество операций, выполненных схематично описанным выше алгоритмом, не превышает <math>O \Bigl( \sum_{i = 0}^k i \binom{k}{i} \cdot |E| \Bigr)</math>, что, очевидно, составляет <math>O(k \; 2^k \cdot |E|)</math>

Полученные алгоритмы, использующие метод цветового кодирования, можно дерандомизировать с небольшой потерей эффективности. Все, что требуется для дерандомизации – это семейство раскрасок графа G = (V, E), такое, что каждому подмножеству k вершин G по крайней мере одной из этих раскрасок назначаются разные цвета. Такое семейство также называется семейством ''идеальных функций хеширования'' от {1, 2, ..., |V|} до {1, 2, ..., k}. Подобное семейство строится явным образом при помощи сочетания методов из работ [1, 9, 12, 16]. Технику дерандомизации, обеспечивающую улучшение с постоянным коэффициентом, см. в работе [5].

'''Лемма 1'''. Пусть G = (V, E) – ориентированный или неориентированный граф, а <math>c: V \to \{ 1, ..., k \}</math> – раскраска его вершин при помощи k цветов. Цветной путь длины k - 1 в графе G, если такой существует, может быть найден за время <math>2^{O(k)} \cdot |E|</math> в наихудшем случае.

'''Лемма 2'''. Пусть G = (V, E) – ориентированный или неориентированный граф, а <math>c: V \to \{ 1, ..., k \}</math> – раскраска его вершин при помощи k цветов. Все пары вершин, соединенные цветными путями длины k - 1 в G, могут быть найдены за время <math>2^{O(k)} \cdot |V| |E|</math> или <math>2^{O(k)} \cdot |V|^{\omega}</math> в наихудшем случае (здесь <math>\omega < 2.376</math> обозначает показатель степени при умножении матриц).

Исходная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (т. е. <math>2^{O(k)} \cdot |E|</math> для ориентированных графов и <math>2^{O(k)} \cdot |V|</math> - для неориентированных) для простых путей фактически применимы к любому ''лесу'' с k вершинами. Граница <math>2^{O(k)} \cdot |V|^{\omega}</math> для простых циклов фактически применима к любому ''серийно-параллельному'' графу с k вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу <math>H = (V_H, E_H)</math>, ''древесная ширина'' которого не превышает t, то такой подграф можно найти за ожидаемое время <math>2^{O(k)} \cdot |V|^{t + 1}</math>, где <math>k = |V_H|</math>. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет <math>k^{O(k)} \cdot |V|^{t + 1}</math>. В качестве специального случая можно сделать вывод, что задача LOG PATH входит в P. Таким образом, на гипотезу Пападимитриу и Яннакакиса [13] можно дать положительный ответ. От экспоненциальной зависимости от k в вышеприведенных границах, вероятно, избавиться не получится, поскольку задача является NP-полной при наличии k во входных данных.

• Имеют ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача булева умножения двух матриц |V| x |V| равными по сложности?

* [[Схемы аппроксимации для задач с планарными графами]]