Czy „Czy permutacja jest automorfizmem grafu w moim zestawie?” NP-kompletny?

Załóżmy, że mamy zestaw S grafów (wykresy skończone, ale ich nieskończona liczba) i grupę P permutacji, która działa na S.

Instancja: permutacja pw P.

Pytanie: Czy istnieje wykres g w S, który dopuszcza automorfizm p?

Czy ten problem NP-zupełny dla niektórych zestawów S?

Łatwo byłoby sprawdzić, czy wykres dopuszcza permutację p (tj. Certyfikat). Ponadto łatwo jest znaleźć przykłady S, w których problem nie jest NP-zupełny, na przykład S jest zbiorem kompletnych wykresów, skąd odpowiedź brzmi zawsze tak.

Uwaga: tak naprawdę nie jestem zainteresowany tym, jakiego rodzaju są to wykresy; jeśli chcesz, mogą być nie-proste, ukierunkowane, kolorowe itp.

DODATEK: Problem, na który obecnie patrzę, polega na klasyfikacji, które izotopizmy są autotopizmami kwadratów łacińskich (które można również interpretować jako specjalny rodzaj automorfizmu grafów).

Biorąc pod uwagę kwadrat łaciński L (i, j), możemy zbudować wykres w następujący sposób:

• Zbiór wierzchołków to zbiór komórek (i, j) w macierzy i
• Istnieje różnica między odrębnymi (i, j) i (i ', j'), ilekroć i = i 'lub j = j' lub L (i, j) = L (i ', j').

Taki wykres nazywa się łacińskim kwadratowym wykresem (patrz np. Ten artykuł Bailey i Camerona http://designtheory.org/library/encyc/topics/lsee.pdf ). Możemy interpretować autotopizm łacińskiego kwadratu jako automorfizm łacińskiego wykresu kwadratowego. Niech więc S będzie zbiorem łacińskich wykresów kwadratowych utworzonych z łacińskich kwadratów rzędu n. Pytanie mnie interesuje:

Biorąc pod uwagę permutację p, czy p jest automorfizmem jednego (lub więcej) wykresów w S?

Mam wrażenie, że odpowiedź na to pytanie jest trudna - piszę obecnie ponad 30 stronicowy artykuł na ten temat (z 2 współautorami). Właściwie przez większość czasu jest to łatwe (przez większość czasu jest to „nie”), ale są pewne trudne przypadki.

Jestem więc zainteresowany znalezieniem problemów decyzyjnych związanych z „klasyfikacją symetrii”. Tak naprawdę nie muszą być powiązane z kwadratami łacińskimi, mam tylko nadzieję, że użyję tych technik, aby odpowiedzieć na pytanie dotyczące kwadratów łacińskich.

$L$$S$

• $x \in L$$|x| = n$$G_x = (V_x,E_x)$$S$$V_x = \{1,2,...,3n\}$$i$$x$$0$$3i-2$$3i-1$$3i-2$$3i$

$p$$\{1,2,...,3n\}$$p$$S$$p$$G_y$$y \in L$$i \in \{1,2,...,n\}$

• $p(3i-2) = 3i-1$$p(3i-1) = 3i-2$$p(3i) = 3i$$i$$y$$0$
• $p(3i-2) = 3i$$p(3i-1) = 3i-1$$p(3i) = 3i-2$$i$$y$$1$

$p$$G \in S$$y$$L$$|p|$$|y|$

$L$