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

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

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

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

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

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

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

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

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

Алгоритми

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

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

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

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

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

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

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

Примітки

1. В оригінальній статті Кука (Cook, 1971), яка містить доведення теореми Кука — Левіна, вже показано, що задача пошуку ізоморфного підграфа NP-повна, зведенням із задачі 3-SAT із використанням клік.
2. Eppstein, 1999, с. 1–27.
3. 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. 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 [ 2017-08-29 у Wayback Machine.]; розширена версія на https://e-reports-ext.llnl.gov/pdf/332302.pdf Архівна копія на сайті Wayback Machine.

Література

• S. A. Cook. . — 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. — .
• David Eppstein. Subgraph isomorphism in planar graphs and related problems // . — 1999. — Т. 3, вип. 3. — arXiv:cs.DS/9911003. — DOI:10.7155/jgaa.00014.
• Michael R. Garey, David S. Johnson. . — W.H. Freeman, 1979. — .. 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. — . — DOI:10.1109/ICDM.2001.989534..
• Miles Ohlrich, Carl Ebeling, Eka Ginting, Lisa Sather. Proceedings of the 30th international Design Automation Conference. — 1993. — . — DOI:10.1145/157485.164556.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics) — . — 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 // . — 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 // . — 2010. — Т. 15. — DOI:10.1145/1671970.1921702.