1294
правки
Цветовое кодирование: различия между версиями
Материал из WEGA
→Литература
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Нахождение маленьких подграфов в больших графах == Постано…») |
KVN (обсуждение | вклад) |
||
| (не показано 16 промежуточных версий 1 участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Цветовое кодирование [2] представляет собой недавно разработанный метод решения за полиномиальное время различных частных случаев проблемы изоморфизма подграфов, которая в общем случае является NP-полной. Входным значением для проблемы изоморфизма подграфов является упорядоченная пара (возможно, ориентированных) графов (G, H). Выходным значением является либо отображение, показывающее, что граф H изоморфен (возможно, порожденному) подграфу G, либо значение | Цветовое кодирование [2] представляет собой недавно разработанный метод решения за полиномиальное время различных частных случаев ''проблемы изоморфизма подграфов'', которая в общем случае является NP-полной. Входным значением для проблемы изоморфизма подграфов является упорядоченная пара (возможно, ориентированных) графов (G, H). Выходным значением является либо отображение, показывающее, что граф H изоморфен (возможно, порожденному) подграфу G, либо значение '''false''' в случае, если такого подграфа не существует. Специальными случаями проблемы изоморфизма подграфов являются задачи нахождения гамильтонова пути, клики и независимого множества, а также многие другие. Представляет интерес задача в случае ''фиксированного'' H. В этом случае целью является разработка алгоритмов, время выполнения которых существенно лучше, чем у наивного алгоритма. | ||
== Описание метода == | == Описание метода == | ||
Метод цветового кодирования является рандомизированным. Вершины графа G = (V, E), в котором | Метод цветового кодирования является рандомизированным. Вершины графа G = (V, E), в котором ищется подграф, изоформный <math>H = (V_H, E_H)</math>, случайным образом раскрашиваются при помощи <math>k = |V_H|</math> цветов. Если <math>|V_H| = O(log \; |V|)</math>, то с небольшой вероятностью, но лишь полиномиально небольшой (т. е. чуть выше полиномиальной) все вершины подграфа G, изоморфного H, если такой подграф существует, будут раскрашены в разные цвета. Такой подграф называется ''цветокодированным''. Метод цветового кодирования использует то обстоятельство, что во многих случаях проще выявить цветокодированные подграфы, чем нераскрашенные. | ||
Возможно, простейший интересный частный случай проблемы изоморфизма подграфов выглядит следующим образом. Пусть даны ориентированный или неориентированный граф G = (V, E) и число k. Содержит ли граф G простой (ориентированный) путь длины k? Содержит ли граф G простой (ориентированный) цикл, длина которого в точности равна k? Далее будет описан алгоритм с временем выполнения | |||
Возможно, простейший интересный частный случай проблемы изоморфизма подграфов выглядит следующим образом. Пусть даны ориентированный или неориентированный граф G = (V, E) и число k. Содержит ли граф G простой (ориентированный) путь длины k? Содержит ли граф G простой (ориентированный) цикл, длина которого ''в точности'' равна k? Далее будет описан алгоритм с временем выполнения <math>2^{O(k)} \cdot |E|</math>, который принимает на вход граф G = (V, E), функцию раскраски <math>c: V \to \{ 1, ..., k \}</math> и вершину <math>s \in V</math> и находит раскрашенный путь длины k – 1, начинающийся в вершине s, если таковой существует. Для поиска раскрашенного пути длины k – 1 в графе G, начинающегося в произвольной вершине, можно добавить к V новую вершину s', раскрасить ее в новый цвет 0 и соединить ребрами со всеми вершинами V, после чего выполнить поиск раскрашенного пути длины k, начинающегося в s'. | |||
Раскрашенный путь длины 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> обозначает показатель степени при умножении матриц). | |||
На основе вышеприведенных лемм были получены следующие результаты. | |||
'''Теорема 3. Простой ориентированный или неориентированный путь длины k - 1 в (ориентированном или неориентированном) графе G = (V, E), содержащем такой путь, может быть найден за ожидаемое время <math>2^{O(k)} \cdot |V|</math> в случае неориентированного графа и за ожидаемое время <math>2^{O(k)} \cdot |E|</math> в случае ориентированного графа.''' | |||
'''Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время <math>2^{O(k)} \cdot |V| |E|</math> либо <math>2^{O(k)} \cdot |V|^{\omega}</math>.''' | |||
Цикл длины k в замкнутых относительно операции взятия минора семействах графов может быть найден при помощи цветового кодирования еще быстрее (для планарных графов чуть более быстрый алгоритм приведен в [6]). | |||
'''Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а <math>k \ge 3</math> – фиксированное целое число. Тогда существует рандомизированный алгоритм, который для заданного графа G = (V, E) из семейства C находит <math>C_k</math> (простой цикл размера k) в G, если таковой существует, за ожидаемое время O(|V|).''' | |||
Как упоминалось выше, все эти теоремы могут быть дерандомизированы с коэффициентом log |V|. Кроме того, эти алгоритмы легко могут быть распараллелены. | |||
== Применение == | |||
Изначальная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (т. е. <math>2^{O(k)} \cdot |E|</math> для ориентированных графов и <math>2^{O(k)} \cdot |V|</math> - для неориентированных) для простых путей фактически применимы к любому ''лесу'' с ''k'' вершинами. Граница <math>2^{O(k)} \cdot |V|^{\omega}</math> для простых циклов фактически применима к любому ''серийно-параллельному'' графу с ''k'' вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу <math>H = (V_H, E_H)</math>, ''древесная ширина'' которого не превышает t, то такой подграф можно найти за ожидаемое время <math>2^{O(k)} \cdot |V|^{t + 1}</math>, где <math>k = |V_H|</math>. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет <math>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>log^2 \; |V|</math>? (Это маловероятно, поскольку в таком случае должен был бы существовать алгоритм, за время <math>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) | |||
[[Категория: Совместное определение связанных терминов]] | |||
