Wysoce regularny wykres i kompletność GI

Nie wiadomo, czy izomorfizm wykres (GI) do silnie graf regularny (SRGs) jest P . Czy są jakieś wskazówki, że może, ale nie musi, być GI -Complete? Czy w takich przypadkach są jakieś poważne konsekwencje? (Podobne do przekonania, że oznaczenie geograficzne może nie być NP-Complete).

— DurgaDatta
źródło

Osobiście uważam, że problem jest ściśle łatwiejszy niż GI, z powodu algorytmu Spielmana dla SRG, który ma mniejszy wykładnik niż Luksa dla grafów ogólnych. Wygląda na to, że jest o wiele więcej struktur! (co ostatecznie może nic nie znaczyć)

— Timothy Sun

Chociaż zgadzam się z @TimothySun, tak naprawdę nie znam formalnych powodów, aby sądzić, że SRGI jest ściśle łatwiejsze niż GI. Na przykład, jeśli nie jest to

reakcji redukcji z Gi SRGI wtedy przyniesie lepsze algorytm GI niż aktualnie znane, lecz w przypadku przepalenia zmniejszenie maksymalnej liczby wierzchołków nawet

to byłoby nie mają tej zaskakującej konsekwencji. Co do twojego drugiego q., Wątpię, czy istnieją jakiekolwiek konsekwencje złożoności jakiegokolwiek problemu (znanego z redukowania do GI) polegającego na uzupełnieniu GI, ponieważ jest on tak niezwiązany z większością innych klas złożoności (w przeciwieństwie do faktu, że GI będący NPC upada PH).

O (n)

$O(n)$

O (n^{3 / 2})

$O(n^{3/2})$

— Joshua Grochow

Wierzę, że wszystkie znane wyniki kompletności GI są funkcyjne (definicja w artykule), a Babai ostatnio wykazał (ITCS 2014, kopia bezpłatnego autora ) - w oparciu o granice struktury grup automorfizmów o silnie regularnych grafach - że nie ma funcjonalizmu redukcja z GI do bardzo regularnego GI.

— Joshua Grochow
źródło