Wysoce regularny wykres i kompletność GI

16

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).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
źródło
6
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
2
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 O ( n- 3 / 2 ), 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(n3)/2))
Joshua Grochow

Odpowiedzi:

11

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