Najszybszy znany algorytm deterministyczny dla problemu niekierowanego graficznego izomorfizmu

Jaki jest najszybszy znany algorytm izomorfizmu grafów bezkierunkowych?

cc.complexity-theory reference-request graph-algorithms graph-isomorphism bbejot
źródło

Myślę, że lepiej, jeśli poprosisz o najszybszy znany algorytm, a nie o poprawność algorytmu podanego w artykule (w szczególności zobacz odpowiednie meta pytanie ). Dla mnie streszczenie jest już czerwoną flagą (wnioski wydają się zawierać również fałszywe informacje).

Juho

Zasadniczo, jeśli główny wynik słynnego problemu jest poprawny, pojawiłby się na znanych blogach poświęconych teorii 1 2 oraz w artykule Wikipedii dotyczącym problemu .

Kaveh

Papier nie przechodzi testu zapachu. Ma na celu rozwiązanie poważnego problemu, ale pojawił się na niejasnej konferencji. Nie ma dowodów. Poprawność jest „potwierdzana” eksperymentalnie. Autorzy uważają, że izomorfizm grafów jest trudny do NP.

Sasho Nikolov

@JoshuaGrochow twierdzi, że najszybszy znany algorytm wymaga czasu

2^{\sqrt{n \log n}}

$2^{\sqrt{n\log n}}$ w tej odpowiedzi cstheory.stackexchange.com/a/22059/4896 . Myślę, że algorytm jest deterministyczny.

Sasho Nikolov

Według dwóch ostatnich prac na ten temat: Szybszy algorytm FPT dla izomorfizmu grafowego sparametryzowanego przez wielokrotność wartości własnych - 2014 r. I przybliżony izomorfizm grafów - 2012 r . Aktualny najszybszy algorytm ma czas działania

2^{O (\sqrt{n \log n})}

$2^{O(\sqrt {n \log n})}$ na wykresach n-wierzchołkowych (wynik Babai i Luksa, 1983)

Marzio De Biasi,

Odpowiedzi:

badania nad izomorfizmem grafów zasadniczo poszły w kierunku poszukiwania wydajnych lub ulepszonych algorytmów dla wielu specjalnych klas grafów z algorytmami P-Time, dla których nastąpił znaczny postęp, a także bardziej empirycznej analizy przy użyciu najnowocześniejszego oprogramowania, np. Nauty osobno patrząc nieco na przeciętne i najgorsze zachowania. dla ogólnego problemu, według ankiety przeprowadzonej na blogu przez Bennetta / Flammię / Harrowa, najwyraźniej najlepiej znany jest stary wynik Babai / Luksa.

„Kanoniczne etykietowanie wykresu” László Babai i Eugene M. Luks STOC 1983 ( tutaj papier ) Opisuje to podwykonanie (lub, no cóż, jak Scott nazwał to?), Exp (-n ^ {frac {1} { 2} + c}), algorytm czasu dla wykresu z n wierzchołkami. Teraz jako lista lektur nie polecam jeszcze przeskakiwać do tego artykułu, ale po prostu chciałem zdławić twój optymizm dla klasycznego algorytmu, pokazując ci (a) to, co ogólnie mamy, to algorytm subwykładniczy, (b) ten rekord istnieje od prawie trzech dekad i (c) że jeśli spojrzysz na papier, zobaczysz, że nie jest to łatwe. Porzucić nadzieję, że wszyscy, którzy wchodzicie?

oto dwa inne dość kompleksowe badania mające na celu ocenę najnowocześniejszych technologii, ale być może bardziej empirycznych.

Efektywne algorytmy testowania izomorfizmu grafów Praca doktorska Jose Luis Lopez Presa (2009)
The Graph Isomorphism Problem (1996) Fortin (1996)

vzn
źródło

Inną kwestią jest to, że tak jak w odpowiedzi JG, Graf-Izomorfizm ma głębokie teoretyczne powiązania z problemem Grupowego Izomorfizmu. widać to na innym blogu na subj autorstwa RJLiptona, Podejście do izomorfizmu grafów

vzn

Zauważ, że badanie Fortin ma prawie 20 lat, co jest wiecznością w dziedzinie, w której na przykład koncepcja kompletności NP ma zaledwie około 40 lat.

David Richerby

tak, zauważył to również, ale istnieje również zjawisko problemów z kluczem / twardym otwarciem TCS wykazujących niewielki znaczący postęp w ciągu dziesięcioleci, oczywiście obejmujących również P vs NP jako kanoniczny przykład tego, a GI pasuje również, jak stwierdzono.

vzn

Wydaje się, że mylisz stwierdzenia „Nie rozwiązaliśmy jeszcze problemu” i „Nie dokonano żadnych postępów”.

David Richerby

Babai wynalazł najszybszy znany algorytm, który działa w czasie quasipolynomialnym $2^{\log n^{O(1)}}$ .

Mohammad Al-Turkistany
źródło

Podobno działa w czasie quasipolynomialnym. Nawet jeśli jego analiza jest wadliwa i ma jedynie sub wykładniczy charakter, nadal będzie to najszybszy algorytm.

Stella Biderman