Задача поиска изоморфного подграфа

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H. Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной[1]. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время[2][3].

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

Задача разрешимости и вычислительная сложность

[править | править код]

Для доказательства, что задача поиска изоморфного подграфа NP-полна, её нужно сформулировать как задачу разрешимости. Входом задачи разрешимости служит пара графов G и H. Ответ задачи положителен, если H изоморфен некоторому подграфу графа G, и отрицателен в ином случае.

Формальное задание:

Пусть , — два графа. Существует ли подграф , такой, что ? Т.е. существует ли отображение , такое, что ?

Доказательство NP-полноты задачи поиска изоморфного подграфа просто и основывается на сведении к этой задаче задачи о клике, NP-полной задачи разрешимости, в которой входом служит один граф G и число k, а вопрос состоит в следующем: содержит ли граф G полный подграф с k вершинами. Для сведения этой задачи к задаче поиска изоморфного подграфа, просто возьмём в качестве графа H полный граф Kk. Тогда ответ для задачи поиска изоморфного подграфа с входными графами G и H равен ответу для задачи о клике для графа G и числа k. Поскольку задача о клике NP-полна, такая полиномиальная сводимость показывает, что задача поиска изоморфного подграфа также NP-полна[4].

Альтернативное сведение от задачи о гамильтоновом цикле отображает граф G, который проверяется на гамильтоновость, на пару графов G и H, где H — цикл, имеющий то же число вершин, что и G. Поскольку задача о гамильтоновом цикле является NP-полной даже для планарных графов, это показывает, что задача поиска изоморфного подграфа остаётся NP-полной даже для планарного случая[5].

Задача поиска изоморфного подграфа является обобщением задачи об изоморфизме графов[англ.], которая спрашивает, изоморфен ли граф G графу H — ответ для задачи об изоморфизме графов «да» тогда и только тогда, когда графы G и H имеют одно и то же число вершин и рёбер и задача поиска изоморфного подграфа для графов G и H даёт «да». Однако статус задачи изоморфизма графов с точки зрения теории сложности остаётся открытым.

Грёгер[6] показал, что если выполнена гипотеза Аандераа — Карпа — Розенберга о сложности запроса[англ.] монотонных свойств графа, то любая задача поиска изоморфного подграфа имеет сложность запроса Ω(n3/2). То есть решение задачи поиска изоморфного подграфа требует проверки существования или отсутствия во входе Ω(n3/2) различных рёбер графа[7].

Ульман[8] описал рекурсивную процедуру с возвратом для решения задачи поиска изоморфного подграфа. Хотя время работы этого алгоритма, в общем случае, экспоненционально, он работает за полиномиальное время для любого фиксированного H (то есть время работы ограничено полиномом, зависящим от выбора H). Если G является планарным графом (или, более обще, графом с ограниченным расширением[англ.]), а H фиксирован, время решения задачи поиска изоморфного подграфа может быть сокращено до линейного времени[2][3].

Ульман[9] существенно обновил алгоритм из статьи 1976 года.

Приложения

[править | править код]

Задача поиска изоморфного подграфа была применена в области хемоинформатики для поиска похожести химических соединений по их структурным формулам. Часто в этой области используется термин подструктурный поиск[8]. Структура запроса часто определяется графически с использованием структурного редактора. Основанные на SMILES базы данных обычно определяют запросы с использованием SMARTS[англ.], расширения SMILES.

Тесно связанные задачи подсчёта числа изоморфных копий графа H в большем графе G используются для обнаружения шаблона в базах данных[10], в биоинформатике взаимодеийствия протеин-протеин[11] и в методах экспоненциальных случайных графов для математического моделирования социальных сетей[12].

Ольрих, Эбелинг, Гитинг и Сатер[13] описали приложение задачи поиска изоморфного подграфа в cистеме автоматизированного проектирования электронных схем. Задача сопоставления подграфа является также подшагом при преобразовании графа (требующего наибольшего времени выполнения), а потому предоставляется инструментальными средствами преобразования графа.

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

Примечания

[править | править код]
  1. В оригинальной статье Кука (Cook 1971), содержащей доказательство теоремы Кука — Левина, уже было показано, что задача поиска изоморфного подграфа NP-полна, путём сведения из задачи 3-SAT с использованием клик
  2. 1 2 Eppstein, 1999, с. 1–27.
  3. 1 2 Nešetřil, Ossona de Mendez, 2012, с. 400–401.
  4. Wegener, 2005, с. 81.
  5. de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013, с. 76–99.
  6. Gröger, 1992, с. 119–127.
  7. Здесь Ω — Омега большое.
  8. 1 2 Ullmann, 1976, с. 31–42.
  9. Ullmann, 2010.
  10. Kuramochi, Karypis, 2001, с. 313.
  11. Pržulj, Corneil, Jurisica, 2006, с. 974–980.
  12. Snijders, Pattison, Robins, Handcock, 2006, с. 99–153.
  13. Ohlrich, Ebeling, Ginting, Sather, 1993, с. 31–37.
  14. http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf Архивная копия от 29 августа 2017 на Wayback Machine; expanded version at https://e-reports-ext.llnl.gov/pdf/332302.pdf Архивная копия от 31 января 2017 на Wayback Machine

Литература

[править | править код]
  • S. A. Cook. Proc. 3rd ACM Symposium on Theory of Computing. — 1971. — doi:10.1145/800157.805047.
  • Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Guillaume Damiand, Christine Solnon. Polynomial algorithms for open plane graph and subgraph isomorphisms // Theoretical Computer Science. — 2013. — Т. 498. — doi:10.1016/j.tcs.2013.05.026. С середины 70-х известно, что задача поиска изоморфного подграфа разрешима в полиномиальное время для планарных графов. Однако, было замечено, что задача поиска подизоморфизма остаётся NP-полной, в частности, поскольку задача о гамильтоновом цикле является NP-полной для планарных графов.
  • Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. — Springer, 2005. — ISBN 9783540210450.
  • David Eppstein. Subgraph isomorphism in planar graphs and related problems // Journal of Graph Algorithms and Applications. — 1999. — Т. 3, вып. 3. — doi:10.7155/jgaa.00014. — arXiv:cs.DS/9911003.
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5.. A1.4: GT48, стр.202.
  • Hans Dietmar Gröger. On the randomized complexity of monotone graph properties // Acta Cybernetica. — 1992. — Т. 10, вып. 3. Архивировано 24 сентября 2015 года..
  • Michihiro Kuramochi, George Karypis. 1st IEEE International Conference on Data Mining. — 2001. — ISBN 0-7695-1119-8. — doi:10.1109/ICDM.2001.989534..
  • Miles Ohlrich, Carl Ebeling, Eka Ginting, Lisa Sather. Proceedings of the 30th international Design Automation Conference. — 1993. — ISBN 0-89791-577-1. — doi:10.1145/157485.164556.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4..
  • N. Pržulj, D. G. Corneil, I. Jurisica. Efficient estimation of graphlet frequency distributions in protein–protein interaction networks // Bioinformatics. — 2006. — Т. 22, вып. 8. — doi:10.1093/bioinformatics/btl030. — PMID 16452112.
  • T. A. B. Snijders, P. E. Pattison, G. Robins, M. S. Handcock. New specifications for exponential random graph models // Sociological Methodology. — 2006. — Т. 36, вып. 1. — doi:10.1111/j.1467-9531.2006.00176.x.
  • Julian R. Ullmann. An algorithm for subgraph isomorphism // Journal of the ACM. — 1976. — Т. 23, вып. 1. — doi:10.1145/321921.321925.
  • Hasan Jamil. 26th ACM Symposium on Applied Computing. — 2011. — С. 1058–1063..
  • Julian R. Ullmann. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism // Journal of Experimental Algorithmics. — 2010. — Т. 15. — doi:10.1145/1671970.1921702.