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

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

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

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

Цветовое кодирование [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) – ориентированный или неориентированный граф, а [math]\displaystyle{ c: V \to \{ 1, ..., k \} }[/math] – раскраска его вершин при помощи k цветов. Раскрашенный путь длины k - 1 в графе G, если такой существует, может быть найден за время [math]\displaystyle{ 2^{O(k)} \cdot |E| }[/math] в наихудшем случае.

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

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

Теорема 3. Простой ориентированный или неориентированный путь длины k - 1 в (ориентированном или неориентированном) графе G = (V, E), содержащем такой путь, может быть найден за ожидаемое время [math]\displaystyle{ 2^{O(k)} \cdot |V| }[/math] в случае неориентированного графа и за ожидаемое время [math]\displaystyle{ 2^{O(k)} \cdot |E| }[/math] в случае ориентированного графа.

Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время [math]\displaystyle{ 2^{O(k)} \cdot |V| |E| }[/math] либо [math]\displaystyle{ 2^{O(k)} \cdot |V|^{\omega} }[/math].

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

Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а [math]\displaystyle{ k \ge 3 }[/math] – фиксированное целое число. Тогда существует рандомизированный алгоритм, который для заданного графа G = (V, E) из семейства C находит [math]\displaystyle{ C_k }[/math] (простой цикл размера k) в G, если таковой существует, за ожидаемое время O(|V|).

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

Применение

Изначальная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (т. е. [math]\displaystyle{ 2^{O(k)} \cdot |E| }[/math] для ориентированных графов и [math]\displaystyle{ 2^{O(k)} \cdot |V| }[/math] - для неориентированных) для простых путей фактически применимы к любому лесу с k вершинами. Граница [math]\displaystyle{ 2^{O(k)} \cdot |V|^{\omega} }[/math] для простых циклов фактически применима к любому серийно-параллельному графу с k вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу [math]\displaystyle{ H = (V_H, E_H) }[/math], древесная ширина которого не превышает t, то такой подграф можно найти за ожидаемое время [math]\displaystyle{ 2^{O(k)} \cdot |V|^{t + 1} }[/math], где [math]\displaystyle{ k = |V_H| }[/math]. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет [math]\displaystyle{ k^{O(k)} \cdot |V|^{t + 1} }[/math]. В качестве специального случая можно сделать вывод, что задача LOG PATH входит в P. Таким образом, на гипотезу Пападимитриу и Яннакакиса [13] можно дать положительный ответ. От экспоненциальной зависимости от k в вышеприведенных границах, вероятно, избавиться не получится, поскольку задача является NP-полной при наличии k во входных данных.

Метод цветового кодирования оказался плодотворным в изучении параметризованных алгоритмов и параметризованной сложности [7, 8]. Недавно этот метод нашел перспективное применение в вычислительной биологии, в частности, в выявлении сигнальных путей в сетях белковых взаимодействий, см. [10, 17, 18, 19].

Открытые вопросы

Перечисленные ниже задачи все еще остаются нерешенными.

• Существует ли (детерминированный или рандомизированный) алгоритм с полиномиальным временем выполнения, определяющий, содержит ли заданный граф G = (V, E) путь длины, скажем, [math]\displaystyle{ log^2 \; |V| }[/math]? (Это маловероятно, поскольку в таком случае должен был бы существовать алгоритм, за время [math]\displaystyle{ 2^{O(\sqrt{n})} }[/math] определяющий, является ли заданный граф с n вершинами Гамильтоновым).

• Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации?

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

Экспериментальные результаты

Результаты выполнения базового алгоритма на биологических данных представлены в работах [17, 19].

См. также

• Аппроксимационные схемы для задач с планарными графами
• Изоморфизм графов
• Древесная ширина графа

Литература

1. Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289-304 (1992)

2. Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42,844-856 (1995)

3. Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209-223 (1997)

4. Bjorklund, A., Husfeldt, T.: Finding a path of superlogarithmic length. SIAM J. Comput. 32(6), 1395-1402 (2003)

5. Chen, J., Lu, S., Sze, S., Zhang, F.: Improved algorithms for path, matching, and packing problems. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 298-307 (2007)

6. Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1 -27 (1999)

7. Fellows, M.R.: New Directions and new challenges in algorithm design and complexity, parameterized. In: Lecture Notes in Computer Science, vol. 2748, p. 505-519 (2003)

8. Flum, J., Grohe, M.: The Parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892-922 (2004)

9. Fredman, M.L., J.Komlos, Szemeredi, E.: Storing a sparse table with O(1) worst case access time. J. ACM 31, 538-544 (1984)

10. HCiffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for Color Coding to facilitate Signaling Pathway Detection. In: Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC), pp. 277-286 (2007)

11. Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25,239-254 (1985)

12. Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. Comput. 22(4), 838-856(1993)

13. Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci. 53(2), 161-170(1996)

14. Plehn, J., Voigt, B.: Finding minimally weighted subgraphs. Lect. Notes Comput. Sci. 484,18-29 (1990)

15. Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309-322 (1986)

16. Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775-786 (1990)

17. Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. J. Comput. Biol. 13(2), 133-144 (2006)

18. Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24, 427-433 (2006)

19. Shlomi,T., Segal, D., Ruppin, E., Sharan, R.:QPath: a method for querying pathways in a protein-protein interaction network. ВМС Bioinform. 7,199 (2006)