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

Цветовое кодирование [2] представляет собой недавно разработанный метод решения за полиномиальное время различных частных случаев ''проблемы изоморфизма подграфов'', которая в общем случае является NP-полной. Входным значением для проблемы изоморфизма подграфов является упорядоченная пара (возможно, ориентированных) графов (G, H). Выходным значением является либо отображение, показывающее, что граф H изоморфен (возможно, порожденному) подграфу G, либо значение '''false''' в случае, если такого подграфа не существует. Специальными случаями проблемы изоморфизма подграфов являются задачи нахождения гамильтонова пути, клики и независимого множества, а также многие другие. Представляет интерес задача в случае ''фиксированного'' H. В этом случае задача заключается в разработке алгоритмов, время выполнения которых существенно лучше, чем у наивного алгоритма.

Метод цветового кодирования является рандомизированным. Вершины графа G = (V, E), в котором ищется изоформный подграф <math>H = (V_H, E_H)</math>, случайным образом раскрашиваются при помощи <math>k = |V_H|</math> цветов. Если <math>|V_H| = O(log \; |V|)</math>, то с небольшой вероятностью, но лишь полиномиально небольшой (т. е. чуть выше полиномиальной) все вершины подграфа G, изоморфного H, если такой подграф существует, будут раскрашены в разные цвета. Такой подграф называется ''цветокодированным''. Метод цветового кодирования использует то обстоятельство, что во многих случаях проще выявить цветокодированные подграфы, чем нераскрашенные.

Цветной путь длины 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) – ориентированный или неориентированный граф, а c V !f {1;  ; kg – раскраска его вершин при помощи k цветов. Цветной путь длины k - 1 в графе G, если такой существует, может быть найден за время 2O( ■ \E\ в наихудшем случае.

На основе вышеприведенных лемм мыли получены следующие результаты.

Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время 2O( ■ \V\ либо \V\<°.

Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а k > 3 – фиксированное целое число. Тогда существует рандомизированный алгоритм, который для заданного графа G = (V, E) из семейства C находит Q (простой цикл размера k) в G, если таковой существует, за ожидаемое время O(|V|).