Задача пошуку ізоморфного підграфа

Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи $G$ і $H$ і потрібно визначити, чи містить $G$ підграф, ізоморфний графу $H$. Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час.

Задача розв'язності та обчислювальна складність

Для доведення, що задача пошуку ізоморфного підграфа NP-повна, її потрібно сформулювати як задачу розв'язності. Входом задачі розв'язності є пара графів $G$ і $H$. Відповідь задачі ствердна, якщо $H$ ізоморфний деякому підграфу графа $G$ і заперенчна в іншому випадку.

Формальна задача: Нехай $G=(V,E)$, $H=(V^{\prime },E^{\prime })$ — два графи. Чи існує підграф $G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})$, такий, що $G_{0}\cong H$? Тобто, чи існує відображення $f\colon V_{0}\rightarrow V^{\prime }$, таке, що $(v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }$?

Доведення NP-повноти задачі пошуку ізоморфного підграфа просте і ґрунтується на зведенні до цієї задачі задачі про кліку, NP-повної задачі розв'язності, в якій входом є один граф $G$ і число $k$, а питання полягає таке: чи містить граф $G$ повний підграф із $k$ вершинами. Для зведення цієї задачі до пошуку ізоморфного підграфа, просто візьмемо як граф $H$ повний граф $K_{k}$. Тоді відповідь задачі пошуку ізоморфного подграфа зі вхідними графами $G$ і $H$ дорівнює відповіді для задачі про кліку для графа $G$ і числа $k$. Оскільки задача про кліку NP-повна, така поліноміальна звідність показує, що задача пошуку ізоморфного підграфа також NP-повна.

Альтернативне зведення задачі про гамільтонів цикл відображає граф $G$, який перевіряється на гамільтоновість, на пару графів $G$ і $H$, де $H$ — цикл, що має таке ж число вершин, як і $G$. Оскільки задача про гамільтонів цикл є NP-повною навіть для планарних графів, то задача пошуку ізоморфного підграфа також залишається NP-повною навіть для планарного випадку.

Задача пошуку ізоморфного підграфа є узагальненням задачі про ізоморфізм графів, у якій запитується, чи граф граф $G$ ізоморфний графу $H$ — відповідь для задачі про ізоморфізм графів «так» тоді й лише тоді, коли графи $G$ і $H$ мають однакове число вершин і ребер та задача пошуку ізоморфного підграфа для графів $G$ та $H$ дає «так». Проте статус задачі ізоморфізму графів з погляду теорії складності залишається відкритим.

Грегер показав, що якщо виконано гіпотезу Аандераа — Карпа — Розенбергапро складність запиту монотонних властивостей графа, то будь-яка задача пошуку ізоморфного підграфа має складність запиту $\Omega (n^{3/2})$. Тобто розв'язання задачі пошуку ізоморфного підграфа вимагає перевірки існування або відсутності у вході $\Omega (n^{3/2})$ різних ребер графа.

Алгоритми

Ульман описав рекурсивну процедуру із поверненням для розв'язання задачі пошуку ізоморфного підграфа. Хоча час роботи цього алгоритму, в загальному випадку, експоненційний, він працює за поліноміальний час для будь-якого фіксованого $H$ (тобто час роботи обмежено поліномом, який залежить від вибору $H$). Якщо $G$ — планарний граф (або, загальніше, граф із обмеженим розширенням), а $H$ — фіксований, час розв'язання задачі пошуку ізоморфного підграфа можна скоротити до лінійного часу.

2010 року Ульман суттєво оновив алгоритм зі статті 1976 року.

Застосування

Задачу пошуку ізоморфного подграфа застосовано в галузі хемоінформатики для пошуку схожості хімічних сполук за їх структурними формулами. Часто в цій галузі використовують термін підструктурний пошук. Структура запиту часто визначається графічно з використанням структурного редактора. Засновані на SMILES бази даних зазвичай визначають запити з використанням SMARTS, розширення SMILES.

Тісно пов'язані задачі підрахунку числа ізоморфних копій графа $H$ у більшому графі $G$ використовуються для виявлення шаблону в базах даних, у біоінформатиці взаємодії протеїн-протеїн і в методах експоненційних випадкових графів для математичного моделювання соціальних мереж.

Ольріх, Ебелінг, Гітинг і Сатер описали затсосування задачі пошуку ізоморфного підграфа в системі автоматизованого проєктування електронних схем. Задача є також підкроком під час перетворення графа (що потребує найбільшого часу виконання), тому надається інструментальними засобами перетворення графа.

До задачі також є інтерес у галузі штучного інтелекту, де її вважають частиною групи завдань зіставлення зі зразком у графах. Також у цій галузі розглядається розширення задачі пошуку ізоморфного графа, відоме як аналіз графа.

Література

• 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. Від середини 1970-х відомо, що задачу пошуку ізоморфного підграфа для планарних графів можна розв'язати за поліноміальний час. Однак, було помічено, що задача пошуку підізоморфізму залишається 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. — arXiv:cs.DS/9911003. — DOI:10.7155/jgaa.00014.
• 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.