Problem izomorfizma grafa

U teorijskom računarstvu, problem izomorfizama podgrafa je računski zadatak u kojem su dva grafikona G i H data kao ulaz, i on mora se utvrditi da li G sadrži podgraf koji je izomorfna H. Izomorfizam podgrafa je generalizacija dva algoritma, algoritma za određivanje problema klike i problema ispitivanja da li graf sadrži Hamiltonov put, pa je stoga NP-kompletan.

Rešenje problema i računarska kompleksnost

Pitanje:

Neka su

G=(V,E)

,

H=(V^{\prime },E^{\prime })

dva grafa. Da li postoji podgraf

G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}=E\cap (V\times V)

takav da je

G_{0}\cong H

? tj. da li postoji

\varphi :V_{0}\rightarrow V^{\prime }

tako da je

(v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }

?

Da bi se dokazalo da je problem NP-kompletan, mora biti formulisan kao problem odlučivanja. Ulaz će onda predstavljati par grafova G i H. Odgovor na problem je pozitivan ako je H izomorfni podgraf od G, a inače je negativan.

Dokaz da je ovaj problrm NP-kompletan je jednostavan i zasniva se na sužavanju problema klika. To je NP-kompletan problem odlučivanja, u kojima je ulaz jedan graf G i broj k, i pitanje je da li G sadrži kompletan podgraf sa k temena. Da bi se ovaj problem kile preveo na nas problem, dovoljno je da je H kompletan graf za K_k, onda je odgovor na problem za G i H jednak odgovoru na klika problem za G i k. Pošto je klika problem je NP-kompletan onda je problem izomorfizma podgrafa takođe je NP-kompletan jer predstavlja sužavanje probleme klike.

Drugi način da se vidi da je problem NP-kompletan je taj što problem Hamiltonovog ciklusa predstavlja uopštenje našeg problema, a taj problem jeste NP-kompletan, pa je i ovaj NP-kompletan.

Izomorfizam podgrafa je generalizacija problema izomorfizam grafa, koji pita da li je G izomorfna H: odgovor na problem izomorfizma grafova važi ako i samo ako G i H imaju isti broj temena i tada problem izomorfizama podgrafa za G i H je tačan. Međutim, teorijska složenost ovog problema ostaje otvoreno pitanje.

Pokazalo se da je složenost ovog problema Ω(n³/2).

Algoritam

Ulman (1976) opisuje rekurzivnu bektreking proceduru za rešavanje ovog problema. Iako mu je vreme izvršavanja , u opštem slučaju, eksponencijalne složenosti, potrebno je polinomijalno vreme kada bi fiksirali H (sa polinoma koji zavisi od izbora H). Kada je G planaran i H fiksiran, vreme izvršavanja algoritma može da se redukuje do linearnog.

Literatura

Cook, S. A. (1971), „The complexity of theorem-proving procedures”, Symposium on Theory of Computing, str. 151—158, doi:10.1145/800157.805047 Tekst „Proc. 3rd ACM Symposium on Theory of Computing ” ignorisan (pomoć).
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 , Arhivirano iz originala (PDF) 21. 05. 2008. g., Pristupljeno 29. 05. 2013 .
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, Arhivirano iz originala (PDF) 24. 09. 2015. g., Pristupljeno 29. 05. 2013 .
Kuramochi, Michihiro; Karypis, George (2001). „Frequent subgraph discovery”. 1st IEEE International Conference on Data Mining. str. 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. str. 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, str. 1058—1063 .