Es "¿Es una permutación p un automorfismo de un gráfico en mi conjunto?" NP-complete?

Supongamos que tenemos un conjunto S de gráficos (gráficos finitos, pero un número infinito de ellos) y un grupo P de permutaciones que actúa sobre S.

Instancia: una permutación p en P.

Pregunta: ¿Existe un gráfico g en S que admite el automorfismo p?

¿Es este problema NP completo para algunos conjuntos S?

Sería fácil comprobar que un gráfico admite la permutación p (es decir, el certificado). Además, es fácil encontrar ejemplos de S donde el problema no es NP-completo, como S es el conjunto de gráficos completos, por lo que la respuesta siempre es sí.

Nota: No estoy realmente interesado en qué tipo de gráficos son; si lo desea, pueden ser no simples, dirigidos, coloreados, etc.

APÉNDICE: El problema que estoy viendo actualmente es clasificar qué isotopismos son autotopismos de cuadrados latinos (que también pueden interpretarse como un tipo especial de automorfismo de grafos).

Dado un cuadrado latino L (i, j) podemos construir una gráfica de la siguiente manera:

El conjunto de vértices es el conjunto de celdas (i, j) en la matriz y
Hay un borde entre distintos (i, j) y (i ', j') siempre que i = i 'o j = j' o L (i, j) = L (i ', j').

Tal gráfico se llama gráfico cuadrado latino (véase, por ejemplo, este artículo de Bailey y Cameron http://designtheory.org/library/encyc/topics/lsee.pdf ). Podemos interpretar un autotopismo de un cuadrado latino como un automorfismo del gráfico del cuadrado latino. Deje que S sea el conjunto de gráficos cuadrados latinos formados a partir de los cuadrados latinos de orden n. Entonces la pregunta que me interesa es:

Dada una permutación p, ¿es p un automorfismo de una (o más) de las gráficas en S?

Mi sensación es que es una pregunta difícil de responder en general: actualmente estoy escribiendo un documento de más de 30 páginas sobre el tema (con 2 coautores). En realidad, la mayoría de las veces es fácil (la mayoría de las veces es "no"), pero hay algunos casos difíciles.

Por lo tanto, estoy interesado en encontrar problemas de decisión que estén relacionados con la "clasificación de simetría". Realmente no necesitan estar relacionados con los cuadrados latinos, solo espero usar estas técnicas para responder la pregunta de los cuadrados latinos.

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

No estoy seguro si entiendo el problema correctamente. ¿Puedes dar un ejemplo de S y P (y la acción grupal de P en S)? Un ejemplo que hace que el problema no sea trivial (ni todo sí o todo no) ayudará a comprender el problema.

Tsuyoshi Ito

En el ejemplo de gráficos completos, lo que no entiendo es cómo actúa una permutación en k puntos en el gráfico completo en n puntos, donde k ≠ n (especialmente si k> n).

Tsuyoshi Ito

Me las arreglé para engañarme y pensar que entendía el problema, pero ahora he decidido que no. ¿Actúa el grupo de permutaciones S en los gráficos de la familia P, o solo actúa potencialmente en los gráficos de la familia P?

Niel de Beaudrap

Un problema aquí es que debemos elegir un conjunto

para el cual las pruebas de membresía estén en NP.

S

$S$

Emil

He agregado un poco más de antecedentes en la respuesta. En realidad, en general, no me importa si el grupo actúa o no en S, siempre y cuando podamos responder "¿es esta permutación un automorfismo de ese gráfico?" En el caso de los cuadrados latinos, podemos interpretarlo como una acción grupal.

Douglas S. Stones

Respuestas:

Tome cualquier lenguaje (que consiste en cadenas binarias). Construya el conjunto de gráficos de la siguiente manera: $L$ $S$

Para cada cadena con , tenemos el gráfico en , con el conjunto de nodos y las siguientes aristas: si el bit de es , entonces los nodos y $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ son adyacentes, de lo contrario y son adyacentes. No hay otros bordes. $3i-1$ $3i-2$ $3i$

Ahora vamos sea una permutación de . Supongamos que es un automorfismo de algún gráfico en . Esto es, es un automorfismo de para algunos . Deje . Consideremos los siguientes dos casos: $p$ $\{1,2,...,3n\}$ $p$ $S$ $p$ $G_y$ $y \in L$ $i \in \{1,2,...,n\}$

, , . Entonces debemos tener un bit de igual a . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Entonces debemos tener un bit de igual a . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

Por lo tanto, si podemos resolver la pregunta "es un automorfismo dado de algún ", también podemos resolver la pregunta "es una cadena dada en ". Además, si podemos hacer lo primero en, digamos, tiempo polinómico en , podemos hacer esto último en tiempo polinómico en también. $p$ $G \in S$ $y$ $L$ $|p|$ $|y|$

Ahora puedes dejar que sea tu problema NP-hard favorito. O el problema de detención ... $L$

Jukka Suomela
fuente

Y para responder realmente a la pregunta original: Sea

un problema NP-completo, y tendrá una

tal que el problema del automorfismo sea NP-completo. El certificado para una respuesta "sí" es un

tal que

es el automorfismo de

, más el 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

@ Jukka: Una forma de acercar la pregunta a la motivación original de los gráficos cuadrados latinos es exigir que el conjunto

de gráficos se cierre bajo isomorfismo. Esto también es una restricción bastante natural. El conjunto

que construyes a partir de un lenguaje arbitrario

no está cerrado bajo isomorfismo y, en este sentido muy específico, es un poco antinatural. No veo cómo modificar su construcción para satisfacer esta restricción, pero creo que sería muy interesante si se pudiera hacer.

S

$S$

S

$S$

L

$L$

Joshua Grochow

@Joshua: Creo que es posible modificar la construcción, por ejemplo de la siguiente manera: tanto los gráficos como las permutaciones que usamos en las consultas consisten en ciclos disjuntos . Más detalladamente,

contiene un ciclo de longitud

si el bit

es igual a

. Del mismo modo, para determinar si

, construya una permutación

que contenga un ciclo de longitud

si el bit

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

. (Podría haber pasado por alto algunos detalles, pero creo que la idea básica debería funcionar ...)

a

$a$

Jukka Suomela

@ Jukka: Bien. Creo que la nueva construcción funciona tal como está escrita (suponiendo que solo permitamos que

actúe en gráficos con exactamente

vértices, y no en gráficos con más de

vértices).

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

Joshua Grochow

@Joshua: Supongo que la posibilidad de aplicar

a gráficos con más de

nodos no importa, si suponemos que el lenguaje

usa un código libre de prefijos.

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$

Jukka Suomela