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.

— Douglas S. Kamienie
źródło

Nie jestem pewien, czy poprawnie rozumiem problem. Czy możesz podać przykład S i P (i działanie grupowe P na S)? Przykład, który sprawia, że problem nie jest błahy (ani „tak”, ani „nie”), pomoże zrozumieć problem.

— Tsuyoshi Ito,

W przykładzie pełnych wykresów nie rozumiem, jak permutacja na k punktach działa na pełnym wykresie na n punktach, gdzie k ≠ n (szczególnie jeśli k> n).

— Tsuyoshi Ito

Udało mi się oszukać, że zrozumiałem problem, ale teraz zdecydowałem, że nie rozumiem. Czy grupa permutacji S działa na wykresach w rodzinie P, czy tylko potencjalnie działa na wykresach w rodzinie P?

— Niel de Beaudrap,

S

$S$

W odpowiedzi dodałem nieco więcej tła. Właściwie to tak naprawdę nie dbam o to, czy grupa działa na S, o ile możemy odpowiedzieć „czy ta permutacja jest automorfizmem tego wykresu?”. W przypadku kwadratów łacińskich możemy interpretować to jako akcję grupową.

— Douglas S. Stones

$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$

— Jukka Suomela
źródło

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

S

$S$

S

$S$

L

$L$

G_{x}

$G_x$

2 i + a + 1

$2i+a+1$

i

$i$

x

$x$

a

$a$

y \in L

$y \in L$

p

$p$

2 i + a + 1

$2i+a+1$

i

$i$

y

$y$

a

$a$

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$