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

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

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

Результаты

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

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

Метод

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

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

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

Пример

В качестве примера возьмём поиск простого цикла длины k в графе ${\displaystyle G=(V,E)}$ .

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

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в V , соединённые простым путём длины k − 1 , а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски ${\displaystyle c\colon V\to \{1,\dots ,k\}}$ для графа G , перенумеруем все разбиения множества цветов ${\displaystyle \{1,\dots ,k\}}$ на два подмножества ${\displaystyle C_{1},C_{2}}$ размера примерно ${\displaystyle k/2}$ в каждом. Для каждого такого разбиения пусть ${\displaystyle V_{1}}$ будет множеством вершинам, выкрашенных цветами из ${\displaystyle C_{1}}$ , а ${\displaystyle V_{2}}$ будет множеством вершин, выкрашенных цветами из ${\displaystyle C_{2}}$ . Пусть ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ обозначают подграфы, порожденные ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$ соответственно. Рекурсивно находим полноцветные пути длины ${\displaystyle k/2-1}$ в ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ . Представим, что булевы матрицы ${\displaystyle A_{1}}$ и ${\displaystyle A_{2}}$ представляют связь каждой пары вершин в ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ полноцветным путём соответственно, и пусть B будет матрицей, описывающей смежность вершин ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$ , тогда булево произведение ${\displaystyle A_{1}BA_{2}}$ даёт все пары вершин в V , соединённые полноцветным путём длины k − 1 . Объединение матриц, полученных на всех разбиениях множества цветов, даёт ${\displaystyle t(k)\leqslant 2^{k}\cdot t(k/2)}$ , что приводит ко времени работы ${\displaystyle 2^{O(k)}\cdot V^{\omega }=O(V^{\omega })}$ . Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и Наора , который и находит, собственно, полноцветный путь.

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

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

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

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

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

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

Приложения

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

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

Примечания

Литература

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

• Alon N., Dao P., Hajirasouliha I., Hormozdiari F., Sahinalp S. C. Biomolecular network motif counting and discovery by color coding // Bioinformatics. — 2008. — Т. 24 , вып. 13 . — С. i241–i249 . — doi : . — . — PMC .
• Hüffner F., Wernicke S., Zichner T. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection // Algorithmica. — 2008. — Т. 52 , вып. 2 . — С. 114–132 . — doi : .