Проблем изоморфизма графа

У теоријском рачунарству, проблем изоморфизама подграфа је рачунски задатак у којем су два графикона G и H дата као улаз, и он мора се утврдити да ли G садржи подграф који је изоморфна H. Изоморфизам подграфа је генерализација два алгоритма, алгоритма за одређивање проблема клике и проблема испитивања да ли граф садржи Хамилтонов пут, па је стога НП-комплетан.

Решење проблема и рачунарска комплексност

Питање:

Нека су $G=(V,E)$, $H=(V^{\prime },E^{\prime })$ два графа. Да ли постоји подграф $G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}=E\cap (V\times V)$ такав да је $G_{0}\cong H$? тј. да ли постоји $\varphi :V_{0}\rightarrow V^{\prime }$ тако да је $(v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }$?

Да би се доказало да је проблем НП-комплетан, мора бити формулисан као проблем одлучивања. Улаз ће онда представљати пар графова G и H. Одговор на проблем је позитиван ако је H изоморфни подграф од G, а иначе је негативан.

Доказ да је овај проблрм НП-комплетан је једноставан и заснива се на сужавању проблема клика. То је НП-комплетан проблем одлучивања, у којима је улаз један граф G и број к, и питање је да ли G садржи комплетан подграф са к темена. Да би се овај проблем киле превео на нас проблем, довољно је да је H комплетан граф за К_k, онда је одговор на проблем за G и H једнак одговорu на клика проблем за G и к. Пошто је клика проблем је НП-комплетан онда је проблем изоморфизма подграфа такође је НП-комплетан јер представља сужавање проблеме клике.

Други начин да се види да је проблем НП-комплетан је тај што проблем Хамилтоновог циклуса представља уопштење нашег проблема, а тај проблем јесте НП-комплетан, па је и овај НП-комплетан.

Изоморфизам подграфа је генерализација проблема изоморфизам графа, који пита да ли је G изоморфна H: одговор на проблем изоморфизма графова важи ако и само ако G и H имају исти број темена и тада проблем изоморфизама подграфа за Г и Х је тачан. Међутим, теоријска сложеност овог проблема остаје отворено питање.

Показало се да је сложеност овог проблема Ω(n³/2).

Алгоритам

Улман (1976) описује рекурзивну бектрекинг процедуру за решавање овог проблема. Иако му је време извршавања , у општем случају, експоненцијалне сложености, потребно је полиномијално време када би фиксирали H (са полинома који зависи од избора H). Када је G планаран и H фиксиран, време извршавања алгоритма може да се редукује до линеарног.

Литература

• Cook, S. A. (1971), „The complexity of theorem-proving procedures”, Symposium on Theory of Computing, стр. 151—158, doi:10.1145/800157.805047  .
• Eppstein, David (1999), „Subgraph isomorphism in planar graphs and related problems” (PDF), Journal of Graph Algorithms and Applications, 3 (3): 1—27, arXiv:cs.DS/9911003  .
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. . A1.4: GT48, pp. 202.
• Gröger, Hans Dietmar (1992), „On the randomized complexity of monotone graph properties” (PDF), Acta Cybernetica, 10 (3): 119—127, Архивирано из оригинала (PDF) 24. 09. 2015. г., Приступљено 29. 05. 2013 .
• Kuramochi, Michihiro; Karypis, George (2001). „Frequent subgraph discovery”. 1st IEEE International Conference on Data Mining. стр. 313. ISBN 978-0-7695-1119-1. doi:10.1109/ICDM.2001.989534. .
• Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993). „SubGemini: identifying subcircuits using a fast subgraph isomorphism algorithm”. Proceedings of the 30th international Design Automation Conference. стр. 31—37. ISBN 978-0-89791-577-9. doi:10.1145/157485.164556. .
• Pržulj, N.; Corneil, D. G.; Jurisica, I. (2006), „Efficient estimation of graphlet frequency distributions in protein–protein interaction networks”, Bioinformatics, 22 (8): 974—980, PMID 16452112, doi:10.1093/bioinformatics/btl030 .
• Snijders, T. A. B.; Pattison, P. E.; Robins, G.; Handcock, M. S. (2006), „New specifications for exponential random graph models”, Sociological Methodology, 36 (1): 99—153, doi:10.1111/j.1467-9531.2006.00176.x .
• Ullmann, Julian R. (1976), „An algorithm for subgraph isomorphism”, Journal of the ACM, 23 (1): 31—42, doi:10.1145/321921.321925 .
• Jamil, Hasan (2011), „Computing Subgraph Isomorphic Queries using Structural Unification and Minimum Graph Structures”, 26th ACM Symposium on Applied Computing, стр. 1058—1063 .