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

Testowanie izomorfizmu grafów asymetrycznych

Odpowiedzi: