El problema de isomorfismo de grafos puede reducirse al problema híbrido de Gowers.
Dado un par $A,B$ de gráficos, cada uno con $n$ vértices, buscamos construir un gráfico $G_{A,B}$ cuya Hamiltonicidad es equivalente a $A$ y $B$ siendo isomorfo. Además, lo construiremos con cuidado para no romper ninguna simetría: si $A,A'$ son isomorfas, y $B,B'$ son isomorfos, entonces también lo son $G_{A,B}$ y $G_{A',B'}$ .
Ahora, dado un problema de isomorfismo de grafos determinado por los grafos $A,B$ consideramos el problema híbrido de Gowers con grafos $G_{A,A}$ y $G_{A,B}$ . Por construcción, estos son isomorfos si $A, B$ son isomorfas. En caso contrario, $G_{A,A}$ es hamiltoniano y $G_{A,B}$ no lo es.
Siempre que podamos realizar dicha construcción en tiempo polinómico, y asegurar que el orden de $G_{A,B}$ es polinómico en $n$ , entonces el isomorfismo de grafos y el problema híbrido de Gowers son igualmente difíciles (es decir, hay una reducción en tiempo polinómico entre ellos).
El resto de esta respuesta se limita a describir esta construcción.
Dejemos que $A,B$ sea un par de grafos en el conjunto de vértices $[n] := \{ 1, 2, \dots, n \}$ . Creamos una variable $v_{a,b}$ para cada par ordenado $(a,b)$ de un vértice en $A$ y un vértice en $B$ . A continuación, escribimos las cláusulas:
- $(\neg v_{a_i,b_j} \lor \neg v_{a_i,b_k}) \forall i,j,k \in [n]$
- $(\neg v_{a_j,b_i} \lor \neg v_{a_k,b_i}) \forall i,j,k \in [n]$
- $(v_{a_i,b_1} \lor v_{a_i,b_2} \lor \cdots \lor v_{a_i,b_n}) \forall i \in [n]$
- $(v_{a_1,b_i} \lor v_{a_2,b_i} \lor \cdots \lor v_{a_n,b_i}) \forall i \in [n]$
que especifican que nuestras variables describen una biyección entre los conjuntos de vértices de $A$ y $B$ . Entonces, para cada arista $(a,a')$ y no de borde $(b,b')$ especificamos la cláusula:
- $(\neg v_{a,b} \lor \neg v_{a',b'})$
y hacer lo mismo con los que no son bordes en $A$ y bordes en $B$ . Esto obliga a nuestras variables a especificar un isomorfismo entre los gráficos $A$ y $B$ .
Ahora, la siguiente página reduce $3$ -SAT a la cobertura de vértices:
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2001/CW/npproof.html
Necesitamos $k$ -SAT en lugar de $3$ -SAT, pero podemos observar que el artilugio en forma de triángulo descrito en esta página puede ser sustituido por un grafo completo de tamaño arbitrario $K_k$ para permitir cláusulas de longitud arbitraria: podemos cubrir las aristas dentro del gráfico completo con $k-1$ vértices (y no menos) siempre que al menos uno de los vértices contiguos $k$ los bordes ya está cubierto.
Hasta ahora, hemos construido un problema de cobertura de vértices de un grafo que (hasta el isomorfismo) sólo depende de los grafos $A, B$ hasta el isomorfismo. Además, tiene una cubierta de vértices del tamaño correcto si y sólo si $A$ y $B$ son isomorfas.
Ahora apela a este resultado:
http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Hamiltonian%20Circuits.pdf
que muestra cómo convertir un problema de cobertura de vértices en un problema de ciclos hamiltonianos, de nuevo canónicamente (por lo que no depende de cómo hayamos etiquetado los vértices de nuestros grafos).
Por lo tanto, podemos construir canónicamente un gráfico $G_{A,B}$ que tiene un ciclo hamiltoniano si y sólo si $A$ y $B$ son isomorfas. Además, $G_{A,B}$ hasta el isomorfismo sólo depende de $A, B$ hasta el isomorfismo. También, $G_{A,B}$ sólo tiene un tamaño polinómico en $n$ (a saber $O(n^4)$ vértices si he contado bien).
El resultado es el siguiente.
