Testowanie izomorfizmu grafów asymetrycznych

Czytając pytanie Przykłady gdzie wyjątkowość rozwiązania sprawia, że łatwiej znaleźć , nowy (? Łatwiej) pytanie przyszło mi do głowy: Właściwie nie wiemy, czy izomorfizm grafów ( ) problem jest w . $GI$ $P$

Ale co się stanie, jeśli założymy, że zarówno i są asymetryczne (tj. Oba mają jedynie trywialny (tożsamość) automorfizm)? Czy problem staje się łatwiejszy (czas wielomianowy)? $G_1$ $G_2$

Uwaga: problem nie może być trudniejszy niż Graph Automorphism ( ), ponieważ istnieje szybka redukcja: wystarczy użyć na , jeśli odpowiedź brzmi tak, to dwa wykresy są izomorficzne (patrz także Johannes Köbler, Uwe Schöning, Jacobo Torán: Wykres Isomorphism jest niski dla PP . 401-411). $GA$ $GA$ $G_1 \cup G_2$

reference-request graph-isomorphism

— Marzio De Biasi
źródło

Przy prawdopodobieństwie zbliżającym się do 1, gdy n rośnie, twój wykres ma tylko trywialny automorfizm według złożoności Kołmogorowa.

— Chad Brewbaker

+1 Ładne pytanie, twoje pytanie potencjalnie prowadzi do ataku na P vs NP. Spróbuj udowodnić, że nie ma redukcji Turinga z

do twojego problemu.

G A

$GA$

— Mohammad Al-Turkistany

Problem ten jest znany jako problem izomorfizmu sztywnego grafu. Jeśli można to rozwiązać w czasie wielomianowym, czy nie, jest on szeroko otwarty. Trwają prace nad atakiem za pomocą algorytmów kwantowych, na przykład poprzez zredukowanie problemu ukrytego przesunięcia ( arxiv.org/abs/quant-ph/0510185 ), ale wyniki są w większości negatywne, co pokazuje, że wypróbowane techniki nie praca.

— Mateus de Oliveira Oliveira

Możliwe jest usztywnienie dowolnego wykresu, tak aby miał tylko jeden endomorfizm (a zatem i automorfizm), poprzez dołączenie wzajemnie sztywnych wykresów do każdego wierzchołka. To implikuje redukcję Turinga z GI do decydującego izomorfizmu grafów asymetrycznych. Niestety, nie jest to wielomian.

— András Salamon

Cóż, Childs / Wocjan nie są sami w używaniu sztywnego oznaczania grafów za pomocą pojedynczego automorfizmu. Istnieje ankieta Babai z 1994 r., Która już sugeruje, że terminologia nie jest standardową www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf. Również w czasach współczesnych sztywny był w tym sensie używany przez Jacobo Torana ( uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf ). Wygląda więc na to, czy autorowi zależy na osadzaniu, czy nie. Ale w odpowiedzi użyłem asymetrii, aby uniknąć zamieszania.

— Mateus de Oliveira Oliveira

Na prośbę Marzio De Biasi przekształcam swój komentarz w odpowiedź.

Wykres jest asymetryczny (niektórzy autorzy nazywają go sztywnym), jeśli ma unikalny automorfizm, tj. Tożsamość. Jak zauważył Chad Brewbacker, większość wykresów jest asymetryczna. Jednak następujące dwa pytania są otwarte:

1) Czy izomorfizm wykresów asymetrycznych w P?

2) Czy izomorfizm grafów ogólnych można sprowadzić do izomorfizmu grafów asymetrycznych?

$\Omega(n\log n)$

— Mateus de Oliveira Oliveira
źródło