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

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

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

Для доведення, що задача пошуку ізоморфного підграфа 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-повна^[4].

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

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

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

Алгоритми

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

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

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

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

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

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

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

Примітки

↑ В оригінальній статті Кука (Cook, 1971), яка містить доведення теореми Кука — Левіна, вже показано, що задача пошуку ізоморфного підграфа NP-повна, зведенням із задачі 3-SAT із використанням клік.
↑ ^а ^б Eppstein, 1999, с. 1–27.
↑ ^а ^б Nešetřil, Ossona de Mendez, 2012, с. 400–401.
↑ Wegener, 2005, с. 81.
↑ de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013, с. 76–99.
↑ Gröger, 1992, с. 119–127.
↑ Тут Ω — омега велике.
↑ ^а ^б Ullmann, 1976, с. 31–42.
↑ Ullmann, 2010.
↑ Kuramochi, Karypis, 2001, с. 313.
↑ Pržulj, Corneil, Jurisica, 2006, с. 974–980.
↑ Snijders, Pattison, Robins, Handcock, 2006, с. 99–153.
↑ Ohlrich, Ebeling, Ginting, Sather, 1993, с. 31–37.
↑ 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. 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.

[1] В оригінальній статті Кука (Cook, 1971), яка містить доведення теореми Кука — Левіна, вже показано, що задача пошуку ізоморфного підграфа NP-повна, зведенням із задачі 3-SAT із використанням клік.

[FOOTNOTEEppstein19991–27-2] а ^б Eppstein, 1999, с. 1–27.

[FOOTNOTENešetřil,_Ossona_de_Mendez2012400–401-3] а ^б Nešetřil, Ossona de Mendez, 2012, с. 400–401.

[FOOTNOTEWegener200581-4] Wegener, 2005, с. 81.

[FOOTNOTEde_la_Higuera,_Janodet,_Samuel,_Damiand,_Solnon201376–99-5] Higuera, Janodet, Samuel, Damiand, Solnon, 2013, с. 76–99.

[FOOTNOTEGröger1992119–127-6] Gröger, 1992, с. 119–127.

[7] Тут Ω — омега велике.

[FOOTNOTEUllmann197631–42-8] а ^б Ullmann, 1976, с. 31–42.

[FOOTNOTEUllmann2010-9] Ullmann, 2010.

[FOOTNOTEKuramochi,_Karypis2001313-10] Kuramochi, Karypis, 2001, с. 313.

[FOOTNOTEPržulj,_Corneil,_Jurisica2006974–980-11] Pržulj, Corneil, Jurisica, 2006, с. 974–980.

[FOOTNOTESnijders,_Pattison,_Robins,_Handcock200699–153-12] Snijders, Pattison, Robins, Handcock, 2006, с. 99–153.

[FOOTNOTEOhlrich,_Ebeling,_Ginting,_Sather199331–37-13] Ohlrich, Ebeling, Ginting, Sather, 1993, с. 31–37.

[14] ttp://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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]