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). Od 2008 godine najbolji algoritam za grafove sa n temena (Eugene Luks, 1983) je složenosti 2^{O(√(n log n))}.

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.

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.

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

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 2^{O(√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.

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.

Specijalni slučajevi

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

• Стабла
• Planarni grafovi (U stvari, izomorfizam planarnih grafova se rešava u logaritamskom vremenu, klasa koja je se nalazi u P)
• Težinski grafovi
• Permutacioni grafovi
• Delimična k-stabla
• Grafovi sa ograničenom vrednošću nekih parametara
  • Grafovi ograničenog roda(Planarni grafovi su grafovi roda 0)
  • Grafovi ograničenog stepena
  • k-kontraktibilni grafovi(uopšteni grafovi ograničenog roda i stepena)
  • 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.

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. 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 $X$ 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. 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 ZPP^NP.. 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:

• direktni grafovii
• etiketirani grafovi, pod uslovom da izomorfizam ne treba da pamti sve etikete, već samo one koje pripadaju temenima sa istim etiketama
• "polarizovani grafovi" (koji se sastoje od kompletnih grafova K_m i praznih grafova i od još nekih grana koje povezuju ta dva grafa; njihov izomorfizam mora da čuva podelu)
• 2-obojivi grafovi
• eksplicitno dati grafovi sa konačnom strukturom
• multigrafovi
• hiper grafovi
• konačno izgenerisani
• Markov proces odlučivanja
• komutativna 3-nilpotentna(primer: xyz=0 za sve elemente x,y,z) polugrupa
• Kontekstno-slobodna gramatika
• Nepotpuno balansirani blok dizajn

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:

• povezani grafovi
• grafovi čiji je dijametar jednak 2 a radius 1
• direktni aciklični grafovi
• regularni grafovi
• bipartitivni grafovi bez ne-trivijalnih regularnih podgrafova
• bipartitivni Ojlerovi grafovi
• bipartitivni regularni grafovi
• linijski grafovi
• split grafovi
• chordal graphs
• regularni samo-komplementarni grafovi

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.
• 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 n². Ova činjenica je interesantna jer je problem pronalaženja (n − ε)-klike u M-grafu veličine n² NP-kompletan za proizvoljno malo ε.
• Problem homeomorfizma 2-kompleksa.

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.
• 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 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⁻¹⁰⁰ ć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. 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.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.

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.