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

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

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

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

Цветовое кодирование [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? Далее будет описан алгоритм с временем выполнения 2°^ Ej, который принимает на вход граф G = (V, E), функцию раскраски c: V !f {1; : : : ; kg и вершину s 2 V и находит раскрашенный путь длины k – 1, начинающийся в вершине s, если таковой существует. Для поиска раскрашенного пути длины k – 1 в графе G, начинающегося в произвольной вершине, можно добавить к V новую вершину s0, раскрасить ее в новый цвет 0 и соединить ребрами со всеми вершинами V, после чего выполнить поиск раскрашенного пути длины k, начинающегося в s0.