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

Цветовое кодирование — Шаблон:Нп5, полезная для обнаружения Шаблон:Не переведено 5. Может быть использована, к примеру, для обнаружения простого пути длины Шаблон:Mvar в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но решение может быть Шаблон:Не переведено 5 без существенного увеличения времени работы.

Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, как в задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину.

Эта техника широко используется в различных областях, включая науку, инженерию, медицину и информатику, для облегчения восприятия и анализа сложной информации.

Метод цветового кодирования предложили и анализировали в 1994 году. Авторы - Нога Алон, Рафаэль Юстер и Юрий ЦвикШаблон:SfnШаблон:Sfn.

Результаты

Следующие результаты могут быть получены методом цветового кодирования:

• Для любой константы Шаблон:Mvar, если граф $G=(V,E)$ содержит цикл размера Шаблон:Mvar, такой цикл может быть найден за:
  • $O(V^{\omega })$ среднее время, или
  • $O(V^{\omega }\log V)$ худшее время, где $\omega$ является экспонентой умножения матриц.
• Для любой константы Шаблон:Mvar и любого графа $G=(V,E)$ из нетривиального семейства графов, замкнутого по минорам (например, планарные графы), если Шаблон:Mvar содержит простой цикл размера Шаблон:Mvar, то такой цикл может быть найден за:
  • Шаблон:Math среднее время, или за
  • Шаблон:Math время в худшем случае.
• Если граф $G=(V,E)$ содержит подграф, изоморфный графу ограниченной древесной ширины, который имеет Шаблон:Math вершин, то такой подграф может быть найден за полиномиальное время.

Метод

Чтобы решить задачу нахождения подграфа $H=(V_H,E_H)$ в данном графе $G=(V,E)$, где Шаблон:Mvar может быть путём, циклом или любым графом с ограниченной древесной шириной, а $|V_H|=O(\log V)$, метод цветового кодирования начинает со случайной раскраски каждой вершины в Шаблон:Mvar с помощью $k=|V_H|$ цветов, а потом пытается найти полноцветную копию Шаблон:Mvar в раскрашенном Шаблон:Mvar. Здесь под полноцветным графом понимается граф, в котором каждая вершина раскрашена в свой цвет. Метод работает путём повторения (1) случайной раскраски графа и (2) нахождения полноцветной копии целевого подграфа. В конечном счёте целевой подграф может быть найден, если процесс повторять достаточное число раз.

Предположим, что копия Шаблон:Mvar в Шаблон:Mvar становится полноцветной с некоторой ненулевой вероятностью Шаблон:Mvar. Отсюда следует, что при повторении случайной раскраски $\frac{1}{p}$ раз эта копия однажды встретится. Заметим, что даже когда вероятность Шаблон:Mvar мала, известно, что при $|V_H|=O(\log V)$ вероятность Шаблон:Mvar лишь полиномиально мала. Предположим, что существует алгоритм, который для данного графа Шаблон:Mvar и раскраски, которая отображает каждую вершину Шаблон:Mvar в один из Шаблон:Mvar цветов, находит копию полноцветной копии Шаблон:Mvar, если она существует, за некоторое время Шаблон:Math. Тогда ожидаемое время поиска копии Шаблон:Mvar в Шаблон:Mvar, если она существует, равно $O(\frac{r}{p})$.

Иногда желательно использовать более жёсткую версию цветной раскраски. Например, в контексте поиска циклов в планарных графах можно разрабатывать алгоритм для поиска хорошо раскрашенных циклов. Здесь под хорошо раскрашенным циклом понимается раскраска последовательными цветами.

Пример

В качестве примера возьмём поиск простого цикла длины Шаблон:Mvar в графе $G=(V,E)$.

При применении метода случайной раскраски каждый простой цикл имеет вероятность $k!/k^k>e^{-k}$ стать полноцветным, поскольку имеется $k^k$ способов выкрасить Шаблон:Mvar вершин цикла, среди которых встречается $k!$ вариантов полноцветной раскраски. Тогда алгоритм (описан ниже) может быть использован для поиска полноцветных циклов в случайно раскрашенном графе Шаблон:Mvar за время $O(V^{\omega })$, где $\omega$ является константой умножения матриц. Тогда требуется полное время $e^k\cdot O(V^{\omega })$ для нахождения простого цикла длины Шаблон:Mvar в Шаблон:Mvar.

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в Шаблон:Mvar, соединённые простым путём длины Шаблон:Math, а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски $c:V\to \{1,\dots ,k\}$ для графа Шаблон:Mvar, перенумеруем все разбиения множества цветов $\{1,\dots ,k\}$ на два подмножества $C_1,C_2$ размера примерно $k/2$ в каждом. Для каждого такого разбиения пусть $V_1$ будет множеством вершинам, выкрашенных цветами из $C_1$, а $V_2$ будет множеством вершин, выкрашенных цветами из $C_2$. Пусть $G_1$ и $G_2$ обозначают подграфы, порожденные $V_1$ и $V_2$ соответственно. Рекурсивно находим полноцветные пути длины $k/2-1$ в $G_1$ и $G_2$. Представим, что булевы матрицы $A_1$ и $A_2$ представляют связь каждой пары вершин в $G_1$ и $G_2$ полноцветным путём соответственно, и пусть Шаблон:Mvar будет матрицей, описывающей смежность вершин $V_1$ и $V_2$, тогда булево произведение $A_{1}B{A}_2$ даёт все пары вершин в Шаблон:Mvar, соединённые полноцветным путём длины Шаблон:Math. Объединение матриц, полученных на всех разбиениях множества цветов, даёт $t(k)⩽2^k\cdot t(k/2)$, что приводит ко времени работы $2^{O(k)}\cdot V^{\omega }=O(V^{\omega })$. Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и НаораШаблон:Sfn, который и находит, собственно, полноцветный путь.

Дерандомизация

Шаблон:Не переведено 5 цветового кодирования вовлекает перечисление возможных раскрашиваний графа Шаблон:Mvar так, что рандомизация раскраски Шаблон:Mvar больше не нужна. Для обнаружения целевого подграфа Шаблон:Mvar в Шаблон:Mvar, перечисление должно включать, по меньшей мере, один случай, где Шаблон:Mvar полноцветн. Чтобы это получить, достаточно перечислить Шаблон:Mvar-совершенное семейство Шаблон:Mvar хеш-функций из $\{1,\dots ,|V|\}$ в Шаблон:Math. По определению, функция Шаблон:Mvar Шаблон:Mvar-совершенна, если для любого подмножества Шаблон:Mvar множества $\{1,\dots ,|V|\}$, где $|S|=k$, существует хеш-функция Шаблон:Mvar из Шаблон:Mvar, такая что $h:S\to \{1,\dots ,k\}$ является Шаблон:Не переведено 5. Другими словами, должна существовать хеш-функци в Шаблон:Mvar, которая раскрашивает заданные Шаблон:Mvar вершин в Шаблон:Mvar различных цвета.

Имеется несколько подходов к построению такого Шаблон:Mvar-идеального семейства хеша:

1. Лучшее явное построение предложили Мони Наор, Леонард Дж. Шульман и Аравинд СринивасанШаблон:Sfn, в котором можно получить семейство размера $e^k{k}^{O(\log k)}\log |V|$. Это построение не требует, чтобы целевой подграф содержался в исходной задаче нахождения подграфа.
2. Другое явное построение предложили Джанетта П. Шмидт и Алан СигельШаблон:Sfn даёт семейство размера $2^{O(k)}{\log }^2|V|$.
3. Ещё одно построение, которое появилось в исходной статье Нога Алона и др.Шаблон:Sfn, можно получить сначала путём построения Шаблон:Mvar-совершенного семейства, которое отображает $\{1,\dots ,|V|\}$ в $\{1,\dots ,k^2\}$, с построением другого Шаблон:Mvar-совершенного семейства, которое отображает $\{1,\dots ,k^2\}$ в $\{1,\dots ,k\}$. На первом шаге можно построить такое семейство с Шаблон:Math случайными битами, которое почти Шаблон:Math-независимоШаблон:SfnШаблон:Sfn, и пространство, необходимое для генерации этих случайных бит, может быть ограничено величиной $k^{O(1)}\log |V|$. На втором шаге, как показали Джанетта П. Шмидт и Алан Зигель Шаблон:Sfn, размер такого Шаблон:Mvar-идеального семейства может быть $2^{O(k)}$. Следовательно, составляя Шаблон:Mvar-идеальные семейства из обоих шагов, можно получить Шаблон:Mvar-совершенное семейство размера $2^{O(k)}\log |V|$, которое отображает из $\{1,\dots ,|V|\}$ в $\{1,\dots ,k\}$.

В случае дерандомизации идеального раскрашивания, когда каждая вершина подграфа раскрашивается последовательно, требуется Шаблон:Mvar-идеальное семейство хэш-функций из $\{1,\dots ,|V|\}$ в $\{1,\dots ,k!\}$. Достаточное Шаблон:Mvar-совершенное семейство, отображающее из $\{1,\dots ,|V|\}$ в $\{1,\dots ,k^k\}$, может быть построено способом, подобным подходу 3 выше (первый шаг). В частности, это делается использованием $nk\log k$ случайных бит, которые почти $k\log k$ независимы, а размер получающегося Шаблон:Mvar-совершенного семейства будет равен $k^{O(k)}\log |V|$.

Дерандомизация метода цветового кодирования может быть легко распараллелена, что приводит к эффективным алгоритмам в классе NC.

Приложения

Недавно цветовое кодирование привлекло внимание ученых из области биоинформатики. Пример — определение сигнальных путей в сетях белок-белкового взаимодействия (ББВ). Другим примером является обнаружение и подсчёт числа Шаблон:Не переведено 5 в сетях ББВ. При изучении как сигнальных путей, так и Шаблон:Не переведено 5 позволяет более глубокое понимание похожести разницы многих биологических функций, процессов и структур в организмах.

Вследствие большого числа генетических данных, которые можно собрать, поиск путей или мотивов может занимать продолжительное время. Однако, используя метод цветового кодирования, мотивы и сигнальные пути с $k=O(\log n)$ вершинами в сети Шаблон:Mvar с Шаблон:Mvar вершинами могут быть найдены очень эффективно за полиномиальное время. Это позволяет исследовать более сложные или больших размеров структуры в сетях ББВ.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья

Литература для дальнейшего чтения

• Шаблон:Статья
• Шаблон:Статья