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[уреди]