Цветовое кодирование

Ключевые слова и синонимы

Нахождение маленьких подграфов в больших графах

Постановка задачи

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

Описание метода

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

Возможно, простейший интересный частный случай проблемы изоморфизма подграфов выглядит следующим образом. Пусть даны ориентированный или неориентированный граф G = (V, E) и число k. Содержит ли граф G простой (ориентированный) путь длины k? Содержит ли граф G простой (ориентированный) цикл, длина которого в точности равна k? Далее будет описан алгоритм с временем выполнения [math]\displaystyle{ 2^{O(k)} \cdot |E| }[/math], который принимает на вход граф G = (V, E), функцию раскраски [math]\displaystyle{ c: V \to \{ 1, ..., k \} }[/math] и вершину [math]\displaystyle{ s \in V }[/math] и находит раскрашенный путь длины k – 1, начинающийся в вершине s, если таковой существует. Для поиска раскрашенного пути длины k – 1 в графе G, начинающегося в произвольной вершине, можно добавить к V новую вершину s', раскрасить ее в новый цвет 0 и соединить ребрами со всеми вершинами V, после чего выполнить поиск раскрашенного пути длины k, начинающегося в s'.

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

Лемма 2. Пусть G = (V, E) – ориентированный или неориентированный граф, а c V !f {1;  ; kg – раскраска его вершин при помощи k цветов. Все пары вершин, соединенные цветными путями длины k - 1 в G, могут быть найдены за время 2O(k) • \V\\E\ или 2o(k) Vj! в наихудшем случае (здесь ! < 2:376 обозначает показатель степени при умножении матриц).

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

Теорема 3. Простой ориентированный или неориентированный путь длины k - 1 в (ориентированном или неориентированном) графе G = (V, E), содержащем такой путь, может быть найден за ожидаемое время 2O( ■ \V\ в случае неориентированного графа и за ожидаемое время 2°^). Ej в случае ориентированного графа.

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

Цикл длины k в замкнутых относительно операции взятия минора семействах графов может быть найден при помощи цветового кодирования еще быстрее (для планарных графов чуть более быстрый алгоритм приведен в [6]).

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

Как упоминалось выше, все эти теоремы могут быть дерандомизированы с коэффициентом log |V|. Кроме того, эти алгоритмы легко могут быть распараллелены.