“A permutação é um automorfismo de um gráfico no meu conjunto?” NP-complete?

Suponha que temos um conjunto S de gráficos (gráficos finitos, mas um número infinito deles) e um grupo P de permutações que atua em S.

Instância: Uma permutação p em P.

Pergunta: Existe um gráfico g em S que admite o automorfismo p?

Esse problema é NP-completo para alguns conjuntos S?

Seria fácil verificar se um gráfico admite a permutação p (isto é, certificado). Além disso, é fácil encontrar exemplos de S onde o problema não é NP-completo, como S sendo o conjunto de gráficos completos, de onde a resposta é sempre sim.

Nota: Não estou realmente interessado em que tipo de gráficos são; se você quiser, pode ser não simples, direcionado, colorido etc.

ADENDO: O problema que estou vendo atualmente é classificar quais isotopismos são autotopismos de quadrados latinos (que também podem ser interpretados como um tipo especial de automorfismo de gráfico).

Dado um quadrado latino L (i, j), podemos construir um gráfico da seguinte maneira:

O conjunto de vértices é o conjunto de células (i, j) na matriz e
Existe uma aresta entre distintas (i, j) e (i ', j') sempre que i = i 'ou j = j' ou L (i, j) = L (i ', j').

Esse gráfico é chamado de gráfico quadrado latino (veja, por exemplo, este artigo de Bailey e Cameron http://designtheory.org/library/encyc/topics/lsee.pdf ). Podemos interpretar um autotopismo de um quadrado latino como um automorfismo do gráfico de quadrados latinos. Então, S seja o conjunto de gráficos quadrados latinos formados a partir dos quadrados latinos da ordem n. Portanto, a pergunta na qual estou interessado é:

Dada uma permutação p, p é um automorfismo de um (ou mais) dos gráficos em S?

Meu sentimento é que é uma pergunta difícil de responder em geral - atualmente estou escrevendo um artigo com mais de 30 páginas sobre o assunto (com 2 co-autores). Na verdade, na maioria das vezes é fácil (na maioria das vezes é "não"), mas existem alguns casos difíceis.

Então, eu estou interessado em encontrar problemas de decisão que estariam relacionados à "classificação de simetria". Eles realmente não precisam estar relacionados aos quadrados latinos, só espero usar essas técnicas para responder à pergunta dos quadrados latinos.

cc.complexity-theory graph-theory np-hardness automorphism Douglas S. Stones
fonte

Não tenho certeza se entendi o problema corretamente. Você pode dar um exemplo de S e P (e a ação de grupo de P em S)? Um exemplo que torna o problema não trivial (nem tudo sim ou tudo não) ajudará a entender o problema.

Tsuyoshi Ito

No exemplo de gráficos completos, o que eu não entendo é como uma permutação em k pontos atua no gráfico completo em n pontos, onde k ≠ n (especialmente se k> n).

Tsuyoshi Ito

Consegui me enganar pensando que havia entendido o problema, mas agora decidi que não. O grupo de permutações S atua nos gráficos da família P, ou apenas potencialmente atua nos gráficos da família P?

Niel de Beaudrap 9/10/10

Uma questão aqui é que precisamos escolher um conjunto

para o qual o teste de associação está no NP.

S

$S$

Emil

Adicionei um pouco mais de experiência na resposta. Na verdade, em geral, eu realmente não me importo se o grupo age ou não em S, desde que possamos responder "essa permutação é um automorfismo desse gráfico?" No caso dos quadrados latinos, podemos interpretá-lo como uma ação de grupo.

Douglas S. Stones

Respostas:

Escolha qualquer idioma (que consiste em cadeias binárias). Construa o conjunto dos gráficos da seguinte maneira: $L$ $S$

Para cada string com , temos o gráfico em , com o conjunto de nodos e as seguintes arestas: se o bit de for , os nós e $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ são adjacentes, caso contrário e são adjacentes. Não há outras arestas. $3i-1$ $3i-2$ $3i$

Agora vamos ser uma permutação de . Assume-se que é um automorphism de alguns gráfico em . Ou seja, é um automorfismo de por algum . Vamos . Vamos considerar os dois casos a seguir: $p$ $\{1,2,...,3n\}$ $p$ $S$ $p$ $G_y$ $y \in L$ $i \in \{1,2,...,n\}$

, , . Então devemos ter o bit de igual a . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Então devemos ter o bit de igual a . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

Portanto, se podemos resolver a questão "é um dado automorphism de alguma ", também podemos resolver a questão "é uma string dada em ". Além disso, se pudermos fazer o primeiro em, digamos, tempo polinomial em , podemos fazer o último em tempo polinomial em também. $p$ $G \in S$ $y$ $L$ $|p|$ $|y|$

Agora você pode deixar ser o seu problema NP-difícil favorito. Ou o problema da parada ... $L$

Jukka Suomela
fonte

E para realmente responder à pergunta original: Seja

um problema completo de NP, e você terá um

tal que o problema de automorfismo seja NP completo. O certificado para uma resposta "sim" é um

tal que

é o automorphism de

, mais o certificado para

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

Jukka Suomela 10/10/10

@Jukka: Uma maneira de aproximar a questão da motivação original dos gráficos quadrados latinos é exigir que o conjunto

de gráficos seja fechado sob isomorfismo. Essa também é uma restrição bastante natural. O conjunto

você constrói a partir de uma linguagem arbitrária

não é fechado sob isomorfismo e, nesse sentido muito específico, é um pouco artificial. Não vejo como modificar sua construção para satisfazer essa restrição, mas acho que seria muito interessante se isso pudesse ser feito.

S

$S$

S

$S$

L

$L$

Joshua Grochow 12/10

@ Josué: Eu acho que é possível modificar a construção, por exemplo, da seguinte forma: os gráficos e as permutações que usamos nas consultas consistem em ciclos separados . Mais detalhadamente,

contém um ciclo de comprimento

se o bit

for igual a

. Da mesma forma, para determinar se

, construa uma permutação

que contenha um ciclo de comprimento

se o bit

for igual a

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$

. (Eu poderia ter esquecido alguns detalhes, mas eu acho que a idéia básica deve funcionar ...)

a

$a$

Jukka Suomela

@Jukka: Legal. Acredito que a nova construção funcione como está escrita (assumindo que apenas permitimos que

atue em gráficos com exatamente

vértices, e não em gráficos com mais de

vértices).

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

Joshua Grochow

@ Josué: Eu acho que a possibilidade de aplicar

em gráficos com mais de

nós não importa, se assumirmos que a linguagem

usa um código sem prefixo?

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$

Jukka Suomela 13/10/10