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 2^{O(√(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 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.^[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 ${\displaystyle 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.^[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 ZPP^NP.^[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 K_m 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 n². Ova činjenica je interesantna jer je problem pronalaženja (n − ε)-klike u M-grafu veličine n² 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⁻¹⁰⁰ ć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]