Grafik izomorfizmi sorunu

Olarak teorik bilgisayar biliminin , grafik izomorfik problemi olan karar problemi verilen iki, oluşur yönsüz grafikler bunlar karar verirken, izomorf aynı olup olmadığını bu zirve adlandırma demek olsa bile, ya da, diğer bir deyişle.

Bu problem özellikle karmaşıklık teorisinde , daha özel olarak P = NP problemi için önemlidir . Aslında, grafik izomorfizmi problemi, ne bir polinom zaman algoritması ne de NP tamlığının bir kanıtı bilmediğimiz NP'nin problemlerinden biridir . NP ara problemi olduğundan şüpheleniliyor . Bununla birlikte, problem belirli grafik sınıfları için polinom zamanda , örneğin düzlemsel grafikler veya sınırlı dereceli grafikler için ve genel durum için yarı-polinom zamanında çözülebilir . Bu problem , alt grafik izomorfizm probleminin bir kısıtlaması olarak görülebilir . G ve H grafiklerinin aynı sayıda köşeye sahip olduğu yer.

Uygulamada, grafik izomorfizmi, kimyada molekülleri sınıflandırmak için kullanılır .

Tanımlar

Bir G grafiğinden H grafiğine bir izomorfizm , G'nin köşeleri kümesinin, kenarlara saygı duyan H'nin köşe kümeleri kümesine bir araya getirilmesidir, yani: G'deki bir kenar ancak ve ancak bir kenarsa içinde H. f{\ displaystyle f}(sen,v){\ displaystyle (u, v)}(f(sen),f(v)){\ displaystyle (f (u), f (v))}

Grafik izomorfizmi sorunu aşağıdaki karar problemidir :

• Giriş: G ve H, iki grafik
• Soru: G ve H izomorfik midir?

Algoritmik

Genel dava

Genel durumda, birkaç algoritmik yaklaşım mevcuttur. En klasik üç tanesi:

• İki izomorfik grafiğin iki eşdeğer köşesinin aynı değere sahip olacağı şekilde, köşelerle ilişkili tamsayılar olan köşe değişmezlerinin kullanımı. Örneğin dereceyi, belirli bir tepe noktasına olan mesafeyi, tepe noktasını içeren maksimum kliğin boyutunu vb. Belirtebiliriz. İki grafik aynı değişmezlere sahip değilse, farklıdırlar. Bu tür bir argümanı rafine edebiliriz, ancak değişmezleri seçmenin her zaman zorluğu vardır ve bu her zaman arama alanını azaltmaz. Ancak iki grafik, bazı uygulamalarda olduğu gibi benzer yapılara sahip değilse, bu tür tekniklerle onu tespit etmek çok hızlıdır.

• İzomorfizmin artımlı yapısı, geriye doğru izleme ( geri izleme ) ile kademeli olarak zirveler ekleyerek .

• Bir kanonik tanımlayıcının her grafiği için hesaplama. Bu yaklaşım, genel cebir sonuçlarının kullanılmasına izin verir . Bir örnek, McKay'in güzellik algoritmasıdır .

Weisfeiler ve Lehman'ın renklendirmenin iyileştirilmesinden oluşan ve teorik bilgisayar biliminin birçok alanıyla bağlantılı olan yönteminden de bahsedebiliriz.

2015 yılına kadar, en iyi bilinen teorik algoritma Luks ve Zemlyachenko'dan kaynaklanıyordu ve bir karmaşıklığı var (burada n , grafiklerden birinin düğüm sayısıdır). 2015'in sonunda Babai, sözde polinom algoritması önerdi ; makale teorik bilgisayar bilimleri topluluğunun dikkatini çekti ve STOC 2016 konferansında en iyi makale ödülünü kazandı . 2Ö(değilgünlük⁡(değil)){\ displaystyle 2 ^ {O \ sol ({\ sqrt {n \ günlük (n)}} \ sağ)}}2lÖg(değil)Ö(1){\ displaystyle 2 ^ {günlük (n) ^ {O \ sol (1 \ sağ)}}}

Özel durum

Sorun, aralarında aşağıdakilerin de bulunduğu birçok grafik sınıfında polinom zamanda çözülebilir:

• Ağaçlar , aralık grafikler , permütasyon grafikleri .
• Düzlemsel grafikleri ve sınırlı tür daha fazla genel olarak grafikler.
• Sınırlı derecenin grafikleri .

Bu algoritmalardan bazıları, büyük çarpımsal sabitler nedeniyle pratikte kullanılamaz, ancak bazı durumlarda, düzlemsel grafikler gibi önemli uygulamaların olduğu durumlarda, verimli algoritmalar ve uygulamalar vardır.

Sınırlı derece veya ağaç genişliği gibi tek parametreye sahip sınıflardaki çoğu algoritma , o parametreye üssel olarak bağlı olan karmaşıklıklara sahiptir. Bu yön, parametreleştirilmiş karmaşıklıkta incelenmiştir . Örneğin k ile sınırlanmış bir ağaç genişliği durumunda formun zaman karmaşıklığını gösterebiliriz . 2Ö(k5lÖg(k))değil5{\ displaystyle 2 ^ {O (k ^ {5} günlük (k))} n ^ {5}}

Karmaşıklık

P ve NP arasında

Grafik izomorfizmi problemi NP sınıfındadır , ancak bu sınıfın bilinen tek problemlerinden biridir ve asal faktör ürün ayrışmasının polinom veya NP-tam olduğu kanıtlanmamıştır. Bu anlamda P = NP problemi için ilginç bir problemdir .

İçinde Aralık 2015László Babai , sorunu çözmek için karmaşıklık sınırını büyük ölçüde azaltan yarı-polinom bir algoritma önermektedir. Bu sonuç, algoritmik bilim topluluğunu hayrete düşürüyor ve karmaşıklık hiyerarşisi üzerindeki etkisi konusunda geniş çapta tartışılıyor.

GI sınıfı

Sorunun bu özel durumu göz önüne alındığında, GI sınıfı ( Grafik İzomorfizmi gibi ) tanıtıldı ve grafik izomorfizm problemine bir polinom indirgemesine sahip tüm problemlerden oluşur . Böylelikle GI-zor ve GI-tam problemden bahsediyoruz.

GI-tam problemleri arasında, yönlendirilmiş grafikler ve hiper grafikler gibi diğer yapılar için izomorfizm problemi ve problemin özel durumları, örneğin normal grafiklerde , kordlarda vb. İzomorfizm vardır .

Diğer sınıflarla ilişkiler

Grafik izomorfizm problemi co-AM'dedir ( Arthur ve Merlin protokolleri tarafından tanımlanan bir sınıf ), bu nedenle problem NP-tamamlanmışsa, polinom hiyerarşisi çöker.

Daha doğrusu, Boppana, Håstad ve Zachos teoremi, eğer ko-NP AM'ye dahil edilirse , o zaman bunun sonucu olarak önceki iddiaya sahip olduğunu verir. Σ2p=Π2p{\ displaystyle \ Sigma _ {2} ^ {p} = \ Pi _ {2} ^ {p}}

Başvurular

Bilgi yayılmayan kanıt

Grafik izomorfizmi problemi, sıfır bilgi ifşası ile kanıtlanmış protokoller tasarlamak için kullanılabilir . Kendimizi, bir A bireyinin başka bir B bireyine belirli bir G grafiğinin 3-rengini bildiğini ancak herhangi bir açık renklendirme yapmak istemediğini kanıtlamak istediği duruma yerleştiririz . Bir sonra göndereceği B grafiği G ' izomorf G ve B iki seçenek arasından rastgele seçecektir:

• A'dan 3- G ' boyaması isteyin  ;
• sormak için A çıkmasını sağlayarak bir eşbiçimlilikle G için 'G .

Bu işlem, her seferinde yeni bir G ' grafiği oluşturarak çok sayıda tekrarlanabilir . Eğer A gerçekten de G'nin 3 rengini tecrübe ederse , her zaman B'nin talebini karşılamayı başaracaktır , ancak gerçeği söylemezse, her yinelemede yalanın keşfedilme şansı ikite birdir (çünkü G ' de değil G'ye izomorfiktir veya A , hiç bilmediği için 3 renk veremez). Yinelemelerden sonra , olası bir yalanın keşfedilmeme olasılığı yalnızca tek bir olasılığa sahiptir . değil{\ displaystyle n}12değil{\ displaystyle {\ frac {1} {2 ^ {n}}}}

Kendi payına, B çıkarsamak olamaz 3-boyama G ne de bundan G ' (bulmak izin veren bir polinom algoritma için G den G' genel durumda bilinmektedir veya bu hesapladýmýz) 3-lekeleme G ' ( çünkü 3-boyama problemi NP-tamamlandı ). Nihayetinde B kendisini, A'nın G'nin 3 rengini bildiğine , ancak onu kendisi inşa edecek hiçbir ipucu olmadığına ikna edebilir.

Bir grafikle ilgili herhangi bir NP-tam sorununun çözümü için böyle bir protokol oluşturmak mümkündür ve herhangi bir NP-tam problemi diğerine dönüştürmek indirgeme ile mümkün olduğundan , böyle bir doğrulama tasarlanabilir. NP-tam sorununun herhangi bir çözümü için protokol.

Kimya

Grafik izomorfizmleri , özellikle moleküllerin atomlar tarafından etiketlenmiş grafikler olarak görülebildiği kimyada ortaya çıkar (yandaki resme bakın). Daha sonra amaçlardan biri, veri tabanlarındaki molekülleri, köşelerin sırası ne olursa olsun, kanonik bir forma sahip olmayı ve izomorfik yapıları yönetmeyi gerektiren her molekül için tek bir girişle sınıflandırmaktır.

Notlar ve referanslar

1. László Babai Quasipolynomial Zamanında Grafik İzomorfizma ArXiV.org üzerinde
2. Bu bölüm Fortin 1996'dan esinlenmiştir .
3. Bu yaklaşım, ayarlanacak birçok parametre nedeniyle bazen kara büyü olarak tanımlanır.
4. Derek G. Corneil ve David G. Kirkpatrick , "  Grafik izomorfizmi problemi için çeşitli buluşsal yöntemlerin teorik analizi  ", SIAM Journal on Computing , cilt.  9 n o  2 {1980}, s.  281-297
5. Brendan D. McKay , "  Pratik grafik izomorfizmi  ", Congressus Numerantium , cilt.  30, bin dokuz yüz Seksen bir, s.  45-87 ( çevrimiçi okuyun ).
6. Vikraman Arvind "  Weisfeiler Lehman Prosedür: İşlemsel Karmaşıklık Kolon  ," Bülteni EATCS , n O  1202016( çevrimiçi okuyun ).
7. Karmaşıklık Bahçesinde (Karmaşıklık Hayvanat Bahçesi) grafik izomorfizmi .
8. Paul J. Kelly , "  Ağaçlar için uygunluk teoremi,  " Pacific J. Math , cilt.  7, 1957, s.  961-968
9. Kellogg S. Booth ve George S. Lueker , "  Aralıklı grafik izomorfizmine karar vermek için doğrusal bir zaman algoritması,  " Journal of the ACM , cilt.  26, n o  2 1979, s.  183-195 ( DOI  10.1145 / 322123.322125 ).
10. Charles J. Colbourn , "  Permütasyon grafiklerinin izomorfizminin test edilmesi üzerine  ", Networks , cilt.  11, bin dokuz yüz Seksen bir, s.  13–21 ( DOI  10.1002 / net.3230110103 ).
11. John E. Hopcroft ve Jin-Kue Wong , "Düzlemsel grafiklerin izomorfizmi için doğrusal zaman algoritması" , Altıncı Yıllık ACM Sempozyumunun Hesaplama Teorisi Bildirilerinde ,1974( DOI  10.1145 / 800119.803896 ) , s.  172–184
12. Gary Miller , "Sınırlı cins grafikleri için izomorfizm testi" , 12. Yıllık ACM Sempozyumu Hesaplama Teorisi Bildirilerinde ,1980( ISBN  0-89791-017-6 , DOI  10.1145 / 800141.804670 ) , s.  225-235.
13. Bkz. Eugene M. Luks , "  Sınırlı değerlik grafiklerinin izomorfizmi polinom zamanında test edilebilir  ", Journal of Computer and System Sciences , cilt.  25,1982, s.  42-65 ( DOI  10.1016 / 0022-0000 (82) 90009-5 ). Bu makale Eugene Luks'ın  (in) 1985 yılında Fulkerson ödülünü almasına yardımcı oldu . Algoritma fikrinin bir açıklaması Fortin 1996 , bölüm 2.3'te bulunabilir.
14. Fortin 1996
15. Örneğin J. Jaja ve SR Kosaraju , "  Düzlemsel grafik izomorfizmi ve ilgili problemler için paralel algoritmalar  ", devreler ve sistemler üzerindeki IEEE işlemleri , cilt.  35, n o  3,1988, s.  304-311Fortin 1996'da alıntılanmıştır
16. "  sınırlı treewidth ait grafiklerle Grafik İzomorfizma  " üzerine, Banach'ın Algoritmik Corner (Varşova Üniversitesi) ,Kasım 2014
17. Quantum dergisi Landmark Algorithm 30 Yıllık Çıkmazı Aşıyor
18. Grafik İzomorfizmi problemi için yeni yarı-polinom zaman çözümünün etkileri nelerdir? mathoverflow web sitesinde.
19. Grafik İzomorfizmi için Quasipolinom Zaman Algoritması: Matematik ∩ Programlama sitesinde Ayrıntılar .
20. Ken Regan, Dick Lipton, "  Grafik İzomorfizma Algoritması Üzerine Biraz Daha  " , Gödel'in Kayıp Mektubu ve P-NP ,Kasım 21, 2015(erişim tarihi 26 Ağustos 2016 ) .
21. Daha kapsamlı bir liste ve bu örneklere referanslar için bkz. Zemlyachenko, Korneenko ve Tyshkevich 1985 .
22. Complexity Zoo'da (in) IM sınıfı
23. Ravi B. Boppana , Johan Håstad ve Stathis Zachos , “  Ortak NP'nin Kısa Etkileşimli Kanıtları Var mı?  », Inf. İşlem. Lett. , cilt.  25, n o  2 1987, s.  127-132
24. Sylvain Perifel , Algoritmik karmaşıklık , Elipsler ,2014, 432  s. ( ISBN  9782729886929 , çevrimiçi okuyun ) , böl.  10.2.5 ("Grafiklerin izomorfizmi sorunu")
25. Paris Bilgisayar Bilimleri Araştırmaları Yüksek Lisans Kursu (MPRI): [1]
26. Goldreich, Micali ve Wigderson 1991 .
27. Bununla birlikte, G'nin problemi verimli bir şekilde nasıl çözeceğimizi bildiğimiz bir grafik sınıfına ait olmaması gereklidir .
28. John W. Raymond, Peter Willett: Kimyasal yapıların eşleştirilmesi için maksimum ortak alt grafik izomorfizma algoritmaları. Bilgisayar Destekli Moleküler Tasarım Dergisi 16 (7): 521-533 (2002)

• (fr) Bu makale kısmen veya tamamen alınır İngilizce Vikipedi başlıklı makalesinde "  Grafik izomorfizması sorun  " ( yazarların listesini görmek ) .

Kaynakça

• (en) Scott Fortin , Grafik izomorfizm problemi (Teknik Rapor 96-20) , Alberta Üniversitesi, Edomonton, Alberta, Kanada,1996( çevrimiçi okuyun )

• (tr) Ronald C. Read ve Derek G. Corneil , Grafik izomorfizm hastalığı , cilt.  1,1977( çevrimiçi okuyun ) , böl.  4, p.  339-363

• (en) VN Zemlyachenko , NM Korneenko ve RI Tyshkevich , "  Graph isomorphism problem  " , Journal of Mathematical Sciences , cilt.  29, n, o  , 4,1985, s.  1426-1481 ( DOI  10.1007 / BF02104746 )