Czy istnieje skuteczny algorytm do określania, czy wykres ma nietrywialny automorfizm?

Pracuję nad problemem związanym z kwadratami łacińskimi i chcę metody, która zasadniczo sprowadza się do problemu decyzyjnego:

Dane wejściowe : skończony, prosty wykres G. Dane
wyjściowe : YESjeśli G ma nietrywialny automorfizm, w NOprzeciwnym razie.

W związku z tym...

Pytanie : Czy istnieje skuteczny algorytm do określania, czy wykres ma nietrywialny automorfizm?

Możemy użyć Nauty lub Bliss (i ewentualnie innych pakietów) do obliczenia całej grupy automorfizmów, ale nie potrzebuję tego; wszystko, co muszę ustalić, to czy jest to banalne.

Jest możliwe, że problem decyzyjny jest teoretycznie równorzędny pod względem złożoności w celu „obliczenia całej grupy automorfizmów” w jakiś sposób. Nie jestem pewny.

Z mojego punktu widzenia „sprawny” oznacza w zasadzie „szybszy w praktyce niż obliczanie całej grupy automorfizmów”, ale interesuje mnie również teoria.

algorithms graphs graph-theory reference-request Rebecca J. Stones
źródło

Jest to równoważne z izomorfizmem grafowym.

Yuval Filmus

@YuvalFilmus O ile mi wiadomo, nie ma znany z redukcji „to izomorficzna ” na „Does posiada nietrywialne automorfizm”. Oczywiście, jeśli następnie ich związek rozłączne posiada nietrywialne automorfizmem (zamiana i ), ale każdy nietrywialna automorfizmem byłoby również nietrywialna automorfizmem .

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

G_{1} ≃ G_{2}

$G_1\simeq G_2$

G_{1}

$G_1$

G_{2}

$G_2$

G_{1}

$G_1$

G_{1} + G_{2}

$G_1+G_2$

David Richerby,

Jeśli chodzi o twoje ostatnie pytanie, jeśli otrzyma się wyrocznię dla GA, można w czasie wielomianowym znaleźć zbiór generujący grupę automorfizmu, wówczas GI redukuje się do GA, co nie jest pewne.

Ariel

@DavidRicherby Co z następującym artykułem? sciencedirect.com/science/article/pii/…

Yuval Filmus

@YuvalFilmus OK, więc używasz redukcji Turinga, a ja korzystam z redukcji wielokrotnych. I wydaje mi się, że redukcje Turinga są bardziej odpowiednie dla kogoś, kto faktycznie próbuje rozwiązać problem.

David Richerby

Odpowiedzi:

Ponieważ interesuje Cię również teoria, która się za tym kryje, podałbym ci quasi-wielomianowy algorytm czasowy dla twojego problemu.

Dla każdej pary wierzchołków (tego samego stopnia) w próbujemy sprawdzić, czy można zamienić i . $u\neq v$ $G$ $u$ $v$

Aby to zrobić, zrób kopię , nazwij to . Teraz usuń z , usuń (kopię) z . $G$ $G'$ $u$ $G$ $v$ $G'$

Następnie dla każdego dołącz do niego bardzo długą ścieżkę, ale tylko wielomianowo długą . $w\in N(u)$

Następnie, do każdej (kopii) dołącz do niej bardzo długą ścieżkę, ale tylko wielomianowo długą . $w\in N(copy\ of\ v)$

Wszystkie wspomniane powyżej bardzo długie ścieżki, ale wielomianowo długie , powinny mieć tę samą długość.

Wywołaj algorytm Babai na wejściu tej nowo wytworzonej pary wykresów.

Jeśli dla dowolnej pary , mamy odpowiedź od Babai, odpowiedz i zatrzymaj się. $(u, v)$ $YES$ $YES$

Jeśli nikt nie zwróci odpowiedzi , odpowiedz i zatrzymaj się. $YES$ $NO$

Oczywiste jest, że dołączenie do wszystkich wierzchołków w i wymusza na izomorfizmie grafowym wewnętrznego mechanizmu działania Babai'a jego algorytmu jedynie mapowanie wierzchołków w do . Tak więc, jeśli odpowiedź jest Babai wtedy możemy bezpiecznie podłączyć z tyłu i mają nietrywialne automorfizmem , ponieważ jest kopią . $N(u)$ $N(v)$ $N(u)$ $N(v)$ $YES$ $u$ $v$ $G$ $G'$ $G$

Złożoność w czasie wykonywania jest wciąż quasi-poli.

Thinh D. Nguyen
źródło