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

Цветовое кодирование [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) – ориентированный или неориентированный граф, а <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> обозначает показатель степени при умножении матриц).

Исходная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (2O( • \E\ для ориентированных графов и 2O ( k ■ \V\ - для неориентированных) для простых путей фактически применимы к любому лесу с k вершинами. Граница 2O( • \V\W для простых циклов фактически применима к любому серийно-параллельному графу с k вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу H = (VH, EH), древесная ширина которого не превышает t, то такой подграф можно найти за ожидаемое время 2O(k) • \V\t+1, где k = JVHJ. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет | Vjt+1. В качестве специального случая можно сделать вывод, что задача LOG PATH входит в P. Таким образом, на гипотезу Пападимитриу и Яннакакиса [13] можно дать положительный ответ. От экспоненциальной зависимости от k в вышеприведенных границах, вероятно, избавиться не получится, поскольку задача является NP-полной при наличии k во входных данных.

• Существует ли (детерминированный или рандомизированный) алгоритм с полиномиальным временем выполнения, определяющий, содержит ли заданный граф G = (V, E) путь длины, скажем, log2 |V|? (Это маловероятно, поскольку в таком случае должен был бы существовать алгоритм, за время 2°^"' определяющий, является ли заданный граф с n вершинами Гамильтоновым).

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

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