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:
- Стабла[10]
- Planarni grafovi[11] (U stvari, izomorfizam planarnih grafova se rešava u logaritamskom vremenu,[12] klasa koja je se nalazi u P)
- Težinski grafovi[13]
- Permutacioni grafovi[14]
- Delimična k-stabla[15]
- Grafovi sa ograničenom vrednošću nekih parametara
- Grafovi ograničenog roda[16](Planarni grafovi su grafovi roda 0)
- Grafovi ograničenog stepena[17]
- k-kontraktibilni grafovi(uopšteni grafovi ograničenog roda i stepena)[18]
- Izomorfizam obojivih grafova sa ograničenom vrednošću boja (većina čvorova imaće istu boju za fiksiranu vrednost boja k) je klase NC, koja je podklasa klase P.[19]
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]
- direktni grafovii[23]
- etiketirani grafovi, pod uslovom da izomorfizam ne treba da pamti sve etikete,[23] već samo one koje pripadaju temenima sa istim etiketama
- "polarizovani grafovi" (koji se sastoje od kompletnih grafova Km i praznih grafova i od još nekih grana koje povezuju ta dva grafa; njihov izomorfizam mora da čuva podelu)[23]
- 2-obojivi grafovi[23]
- eksplicitno dati grafovi sa konačnom strukturom[23]
- multigrafovi[23]
- hiper grafovi[23]
- konačno izgenerisani[23]
- Markov proces odlučivanja[24]
- komutativna 3-nilpotentna(primer: xyz=0 za sve elemente x,y,z) polugrupa[23]
- Kontekstno-slobodna gramatika[23]
- Nepotpuno balansirani blok dizajn[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]
- povezani grafovi[23]
- grafovi čiji je dijametar jednak 2 a radius 1[23]
- direktni aciklični grafovi[23]
- regularni grafovi[23]
- bipartitivni grafovi bez ne-trivijalnih regularnih podgrafova[23]
- bipartitivni Ojlerovi grafovi[23]
- bipartitivni regularni grafovi[23]
- linijski grafovi[23]
- split grafovi[25]
- chordal graphs[23]
- regularni samo-komplementarni grafovi[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".
- Ako je odgovor "da":
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]
Референце уреди
- ^ 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, S2CID 1658062, arXiv:cs.CG/0601002
, doi:10.1145/1346330.1346336
- ^ Johnson 2005
- ^ Babai & Codenotti 2008
- ^ 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
- ^ McKay 1981
- ^ Ullman 1976
- ^ Cristopher Moore; Russell, Alexander; Schulman, Leonard J. (2005). „The Symmetric Group Defies Strong Fourier Sampling: Part I”. arXiv:quant-ph/0501056v3 [quant-ph].
- ^ László Babai, William Kantor, Eugene Luks, Computational complexity and the classification of finite simple groups, Proc. 24th FOCS (1983). стр. 162.–171.
- ^ P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism Архивирано на сајту Wayback Machine (24. септембар 2015), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
- ^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; Aho, Hopcroft & Ullman 1974
- ^ Hopcroft & Wong 1974
- ^ Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian (2009). „Planar Graph Isomorphism is in Log-Space”. 2009 24th Annual IEEE Conference on Computational Complexity. стр. 203—214. ISBN 978-0-7695-3717-7. doi:10.1109/CCC.2009.16.
- ^ Booth & Lueker 1979
- ^ Colbourn 1981
- ^ Bodlaender 1990
- ^ Miller 1980; Filotti & Mayer 1980
- ^ Luks 1982
- ^ 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.)
- ^ Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.
- ^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993
- ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
- ^ Arvind & Köbler 2000
- ^ а б в г д ђ е ж з и ј к л љ м н њ о п р с т ћ Zemlyachenko, Korneenko & Tyshkevich 1985
- ^ "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.
- ^ 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.
- ^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29.
- ^ Kozen 1978
- ^ J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 - 132 .
- ^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson 2005
- ^ Designing Programs that Check their Work
- ^ Christophe-André Mario Irniger. Graph Matching: Filtering Databases of Graphs Using Machine Learning. 2005. ISBN 978-1-58603-557-0.
- ^ Cook, Diane J.; Holder, Lawrence B. (2006). Mining Graph Data. John Wiley & Sons. стр. 120—122. ISBN 978-0-470-07303-2.
- ^ Baird, HS; Cho, YE (1975). An artwork design verification system. Proceedings of the 12th Design Automation Conference. IEEE Press. стр. 414—420.
Literatura уреди
- Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley.
- Arvind, Vikraman; Köbler, Johannes (2000), „Graph isomorphism is low for ZPP(NP) and other lowness results.”, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 1770, Springer-Verlag, стр. 431—442, ISBN 978-3-540-67141-1, OCLC 43526888.
- Arvind, Vikraman; Kurur, Piyush P. (2006), „Graph isomorphism is in SPP”, Information and Computation, 204 (5): 835—852, doi:10.1016/j.ic.2006.02.002.
- Babai, László; Codenotti, Paolo (2008). „Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time”. FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society. стр. 667—676. ISBN 978-0-7695-3436-7..
- Babai, László; Grigoryev, D. Yu.; Mount, David M. (1982), „Isomorphism of graphs with bounded eigenvalue multiplicity”, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, стр. 310—324, ISBN 978-0-89791-070-5, S2CID 12837287, doi:10.1145/800070.802206.
- Bodlaender, Hans (1990), „Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees”, Journal of Algorithms, 11 (4): 631—643, doi:10.1016/0196-6774(90)90013-5.
- Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.
- Booth, Kellogg S.; Lueker, George S. (1979), „A linear time algorithm for deciding interval graph isomorphism”, Journal of the ACM, 26 (2): 183—195, S2CID 18859101, doi:10.1145/322123.322125.
- Boucher, C.; Loker, D. (2006), Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs (PDF), University of Waterloo, Technical Report CS-2006-32.
- Colbourn, C. J. (1981), „On testing isomorphism of permutation graphs”, Networks, 11: 13—21, doi:10.1002/net.3230110103.
- Filotti, I. S.; Mayer, Jack N. (1980), „A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 236—243, ISBN 978-0-89791-017-0, S2CID 16345164, doi:10.1145/800141.804671.
- 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, OCLC 11745039.
- Hopcroft, John; Wong, J. (1974), „Linear time algorithm for isomorphism of planar graphs”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, стр. 172—184, S2CID 15561884, doi:10.1145/800119.803896.
- Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), „Graph isomorphism is low for PP”, Computational Complexity, 2 (4): 301—330, S2CID 8542603, doi:10.1007/BF01200427.
- Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287.
- Kozen, Dexter (1978), „A clique problem equivalent to graph isomorphism”, ACM SIGACT News, 10 (2): 50—52, S2CID 52835766, doi:10.1145/990524.990529.
- Luks, Eugene M. (1982), „Isomorphism of graphs of bounded valence can be tested in polynomial time”, Journal of Computer and System Sciences, 25: 42—65, doi:10.1016/0022-0000(82)90009-5.
- McKay, Brendan D. (1981), „Practical graph isomorphism”, Congressus Numerantium, 30: 45—87, 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980).
- Miller, Gary (1980), „Isomorphism testing for graphs of bounded genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 225—235, ISBN 978-0-89791-017-0, S2CID 13647304, doi:10.1145/800141.804670.
- Schmidt, Douglas C.; Druffel, Larry E. (1976), „A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices”, J. ACM, ACM, 23 (3): 433—445, ISSN 0004-5411, S2CID 6163956, doi:10.1145/321958.321963.
- Spielman, Daniel A. (1996). „Faster isomorphism testing of strongly regular graphs”. STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM. стр. 576–584. ISBN 978-0-89791-785-8..
- Ullman, Julian R. (1976), „An algorithm for subgraph isomorphism”, Journal of the ACM, 23: 31—42, S2CID 17268751, doi:10.1145/321921.321925.
Ankete i monografije уреди
- Read, Ronald C.; Corneil, Derek G. (1977), „The graph isomorphism disease”, Journal of Graph Theory, 1 (4): 339—363, MR 0485586, S2CID 26589776, doi:10.1002/jgt.3190010410..
- Gati, G. "Further annotated bibliography on the isomorphism disease." – Journal of Graph Theory 1979, 3, 95-109.
- Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), „Graph isomorphism problem”, Journal of Mathematical Sciences, 29 (4): 1426—1481, S2CID 121818465, doi:10.1007/BF02104746. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118. (1982). стр. 83–158.)
- Arvind, V.; Jacobo Torán (2005), „Isomorphism Testing: Perspectives and Open Problems” (PDF), Bulletin of the European Association for Theoretical Computer Science (86): 66—84, Архивирано из оригинала (PDF) 27. 07. 2011. г., Приступљено 26. 05. 2015. (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups.)
- Köbler, Johannes; Schöning, Uwe; Jacobo Torán (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 978-0-8176-3680-7, OCLC 246882287. (From the book cover: The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.)
- Johnson, David S. (2005), „The NP-Completeness Column”, ACM Transactions on Algorithms, 1 (1): 160—176, S2CID 12604799, doi:10.1145/1077464.1077476. (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.)
- Torán, Jacobo; Fabian Wagner (2009), „The Complexity of Planar Graph Isomorphism” (PDF), Bulletin of the European Association for Theoretical Computer Science (97), Архивирано из оригинала (PDF) 20. 09. 2010. г., Приступљено 26. 05. 2015.
Softver уреди
- Graph Isomorphism, review of implementations, The Stony Brook Algorithm Repository.