Problem izomorfizma grafova

Из Википедије, слободне енциклопедије

Problem izomorfizma grafova je računarski problem utvrđivanja da li su dva konačna grafa izomorfna.

Pored praktičnog značaja, problem izomorfizma grafova je veoma zanimljiv u računarskoj teoriji kompleksnosti kao jedan od retkih problema koji pripadaju NP, za koji se ne zna da li je rešiv u polinomijalnom vremenu niti da li je NP-kompletan: jedan je od 12 problema koji se nalaze na listi Garey & Johnson (1979), i jedan od samo dva problema čija kompleksnost ostaje nerešiva (drugi je Rastavljanje na faktore)[1]. Od 2008 godine najbolji algoritam za grafove sa n temena (Eugene Luks, 1983) je složenosti 2O(√(n log n)).[2][3]

Poznato je da se problem izomorfizma grafova nalazi na nižem nivou hijerarhije klase NP, što govori da nije NP-kompletan osim ako na lestvici polinomijalnog vremena ne dostiže drugi nivo.[4]

Istovremeno, izomorfizam za neke specijalne grafove može biti rešen u polinomijalnom vremenu, a u praksi izomorfizam grafova se obično efikasno rešava.[5]

Ovaj problem je specijalna vrsta problema izomorfizma podgrafa[6], za koji se zna da je NP-kompletan. Poznat je kao specijalan slučaj problema ne-abelove skrivene podgrupe preko simetričnih grupa.[7]


Istorija[уреди]

Sadašnji najbolji algoritam je algoritam koji je osmislio Eugene Luks (1983) i baziran je na ranijim radovima Luksa (1981), Babaija i Luksa (1982) kombinovan sa podfaktorijalnim algoritmom Zemljašenka. Algoritam je zasnovan na klasifikaciji konačnih prostih grupa. Bez ove klasifikacije CFSG, dobijena je nesto slabija granica 2O(√n log2 n),prvo za jake regularne grafove Lazlo Bablai , (1980), a zatim su je Babai i Luks (1982) proširili na opšte grafove. Poboljšanje eksponenta √n je glavni otvoreni problem; za jake regularne grafove to je rešio Spielman (1996) (1996). Za hipergrafove ograničenog ranga,gde subeksponencijalna gornja granica odgovara slučaju grafova, rešenje/odgovor su nedavno našli Babai i Cadenotti.

Problem izomorfizma grafova je računski ekvivalentan problemu izračunavanja automorfizma grupe grafa, i slabiji je od problema izomorfizma permutacionih grupa, i od problema preseka permutacionih grupa. Za poslednja dva problema Babai, Kantor i Luks (1983) su dobili granice složenosti slične onima za izomorfizam grafova.[8]

Postoji nekoliko konkurentnih praktičnih algoritama za izomorfizme grafova,koje su postavili McKay (1981), Schmidt & Druffel (1976), Ullman (1976), i tako dalje. Iako deluje da se izvršava dobro na slučajnim grafovima,glavni nedostatak ovih algoritama je njihova eksponencijalna vremenska složenost u najgorem slučaju.[9]

Specijalni slučajevi[уреди]

Lista specijalnih slučajeva problema izomorfizma grafova, koji imaju efikasno rešenje u polinomijalnom vremenu:

Složena klasa GI[уреди]

Pošto se za problem izomorfizma grafova ne zna da li je NP-kompletan, niti da li je obradiv, istraživači su nastojali da steknu bolji uvid u ovaj problem definisanjem nove klase GI, kroz niz problema koji su rešivi u polinomijalnom vremenu.[20] U stvari ako bi problem izomorfizma grafova bio rešiv u polinomijalnom vremenu onda bi GI klasa bila jednaka sa P

Kao što je uobičajeno za kompleksne klase koje se rešavaju u polinomijalnom vremenu, problem se naziva GI-težak ako postoji Tjuringova redukcija bilo kog problema GI klase do tog problema u polinomijalnom vremenu, odnosno polinomijalno-vremensko rešenje nekog GI-teškog problema bi se dobilo uz pomoć problema izomorfizma grafova koji se takođe rešava u polinomijalnom vremenu (ovo važi za sve probleme GI klase). Problem je kompletan za GI, ili je GI-kompletan

Problem izomorfizma grafova sadržan je u NP i co-AM. GI je manje isadržan i/u Parity P, a takođe je deo potencijalno mnogo manje klase SPP.[21] To da leži u Parity P znači da problem izomorfizma grafova nije ništa teži od određivanja da li je polinomijalno-vreme uopšte moguće determinisati. Tjuringova mašina ima paran ili neparan broj prihvatanja putanja. GI je takođe sadržan i nizak za ZPPNP.[22]. Ovo suštinski znači da efikasan Las Vegas algoritam sa pristupom NP oraklu može da reši izomofizme grafova tako lako, da čak ne dobija nikakvu moć sticanjem mogućnosti da to uradi u konstantnom vremenu.

GI-kompletni i GI-teški problemi[уреди]

Problem izomorfizma nekih drugih objekata[уреди]

Postoji veliki broj klasa matematičkih objekata za koje je problem izomorfizma grafova GI-kompletan. Neki od njih su grafovi sa nekim dodatnim svojstvima ili ograničenjima:[23]

GI-kompletne klase grafova[уреди]

Klasa grafova se naziva GI-kompletna ako je problem izomorfizma grafova iz ove grupe GI-kompletan. Sledeće klase su GI-kompletne:[23]

Ova lista nije upotpunjena! Dosta klasa digrafova takodje su GI-kompletne.

Ostali GI-kompletni problemi[уреди]

Postoje i neki drugi netrivijalni GI-kompletni problemi pored problema izomorfizma grafova:

  • Pronalaženje samo-komplementarnih grafova ili digrafova.[26]
  • Problem klike za takozvanu klasu M-grafova. Pokazalo se da je pronalaženje izomorfizma za n-najviše tačke grafova ekvivalentno pronalaženju n-klika u M-grafu veličine n2. Ova činjenica je interesantna jer je problem pronalaženja (nε)-klike u M-grafu veličine n2 NP-kompletan za proizvoljno malo ε.[27]
  • Problem homeomorfizma 2-kompleksa.[28]

GI-teški problemi[уреди]

  • Problem brojanja izomorfizma između dva grafa je polinomijalnog vremena ekvivalentan problemu koji govori da li neki od ta dva grafa uopšte postoji.[29]
  • Problem odlučivanja da li dva konveksna politopa dobijena ili V-opisom ili H-opisom su " projectively or affinely izomorfni", što znači da postoji projective or affine mapa između prostora koji sadrže dva politopa (ne nužno istih dimenzija) koje uključuje bijaiciju između dva politopa.

Provera programa[уреди]

Blum and Kannan[30] su predstavili program koji proverava izomorfizme grafova. Uzmimo da se za P tvrdi da je polinomijalno-vremenska procedura koja proverava da li su dva grafa izomorfna, ali nije pouzdan. Da bi se proverilo da li su G i H izomorfni:

  • Pitati P da li su G i H izomorfni.
    • Ako je odgovor "da":
      • Pokušati konstruisanje izomorfizma koristeći P kao subrutinu. Označiti teme u G i v u H, I modifikovati grafove kako bi postali različiti (sa malom lokalnom promenom). Pitati P da li su modifikovani grafovi izomorfni. Ako ne, pomeriti v na drugo teme/vertex. Nastaviti sa pretragom.
      • Izomorfizam ili će biti pronađen (i moći će da bude verifikovan) ili će P protivrečiti sam sebi.
    • Ako je odgovor "ne":
      • Izvesti sledeće 100 puta. Izabrati nasumično G ili H, i nasumično permutovati njihova temena(vertices). Pitati P da li je graf izomorfanza G i H. (kao u AM protokolu za neizomorfizam grafova).
      • Ako bilo koji od od testova budu negativni, oceniti P kao neispravan(invalid) program. U suprotnomo dgovor je "ne".

Ova procedura je polinomijalno-vremenska,i daje ispravan odgovor ako je P tačan program za izomorfizme grafova. Ako P nije odgovarajući program ali ispravno odgovori na G i H,kontrola će ili dati tačan odgovor, ili će detektovati nevažeće ponašanje P.Ako P nije odgovarajući program, a netačnoodgovorinaG i H,kontrolaćesavelikomverovatnoćom,detektovatineispravnoponašanjekod P, a sa verovatnoćom 2−100 će odgovoriti pogrešno.

Napomena,P je korišćen samo kao 'blackbox'.

Primene[уреди]

U heminformatici i matematičkoj hemiji, testiranje izomorfizma grafova koristi se za pronalaženje hemijskog jednjenja u hemijskoj bazi.[31] Takođe, u organskoj matematičkoj hemiji testiranje izomorfizma grafova korisno je za generazicione molekularne grafove i za kompijutersku sintezu.

Pretraga hemijske baze je primer analize podataka pomoću grafova u kojem se pristup kanonizacije grafova često koristi.[32]Jedan broj identifikatora za hemijske supstance kao što su SMILES i InChI, koji su napravljeni da obezbede standardizovani čitljiv način za kodiranje molekularnih informacija kao i da omogući pretragu takvih informacija u bazama podataka na internetu,koriste kanonizacijski korak u svom računanju, što je u suštini kanonizacija grafa koji predstavlja molekul. U automatizaciji elektronskog dizajna, izomorfizam grafova je osnova Layout Versus Schematic (LVS) circuit design step, koji verifikuje da li su električno kolo predstavljena prikladnom shemom i shema integrisanog kola iste.[33]

Референце[уреди]

  1. The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2): 1, arXiv:cs.CG/0601002Слободан приступ, doi:10.1145/1346330.1346336 
  2. Johnson (2005)
  3. Babai & Codenotti (2008)
  4. Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114-124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312-323
  5. McKay (1981)
  6. Ullman (1976)
  7. Cristopher Moore; Russell, Alexander; Schulman, Leonard J. (2005). „The Symmetric Group Defies Strong Fourier Sampling: Part I”. arXiv:quant-ph/0501056v3Слободан приступ [quant-ph]. 
  8. László Babai, William Kantor, Eugene Luks, Computational complexity and the classification of finite simple groups, Proc. 24th FOCS (1983). стр. 162.–171.
  9. P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
  10. P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; Aho, Hopcroft & Ullman (1974)
  11. Hopcroft & Wong (1974)
  12. doi:10.1109/CCC.2009.16
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  13. Booth & Lueker (1979)
  14. Colbourn (1981)
  15. Bodlaender (1990)
  16. Miller (1980); Filotti & Mayer (1980)
  17. Luks (1982)
  18. Gary L. Miller: Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus). Proc. Int. Conf. on Foundations of Computer Theory, (1983). стр. 310-327 (Lecture Notes in Computer Science, vol. 158, full paper in: Information and Control, 56(1-2):1–20, 1983.)
  19. Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.
  20. Booth & Colbourn (1977); Köbler, Schöning & Torán (1993)
  21. Köbler, Schöning & Torán (1992); Arvind & Kurur (2006)
  22. Arvind & Köbler (2000)
  23. 23,00 23,01 23,02 23,03 23,04 23,05 23,06 23,07 23,08 23,09 23,10 23,11 23,12 23,13 23,14 23,15 23,16 23,17 23,18 23,19 23,20 23,21 23,22 Zemlyachenko, Korneenko & Tyshkevich (1985)
  24. "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008). стр. 688-696.
  25. Chung, Fan RK (1985). „On the cutwidth and the topological bandwidth of a tree”. SIAM Journal on Algebraic Discrete Methods. 6 (2): 268—277. doi:10.1137/0606026. Приступљено 13. 4. 2015. 
  26. Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29.
  27. Kozen (1978)
  28. J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 - 132 .
  29. R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson (2005)
  30. Designing Programs that Check their Work
  31. Christophe-André Mario Irniger . "Graph Matching: Filtering Databases of Graphs Using Machine Learning". 2005. ISBN 978-1-58603-557-0.
  32. Cook, Diane J.; Holder, Lawrence B. (2006). Mining Graph Data. John Wiley & Sons. стр. 120—122. ISBN 978-0-470-07303-2. 
  33. Baird, HS; Cho, YE (1975). An artwork design verification system. Proceedings of the 12th Design Automation Conference. IEEE Press. стр. 414—420. 

Литература[уреди]

Reference[уреди]

Ankete i monografije[уреди]

Softver[уреди]