Una combinación de dos problemas de complejidad bien conocidos

Question

Supongamos que nos dan dos gráficos $G$ y $H$ y se les dice que se da una de las dos situaciones siguientes. O bien son isomorfas, o bien una de las gráficas contiene un ciclo de Hamilton y la otra no. ¿Se puede saber en tiempo polinómico en qué situación se encuentran? Obviamente se puede si el isomorfismo del grafo es fácil o si encontrar ciclos de Hamilton es fácil, así que vamos a suponer que ambas son difíciles.

Puede que haya una respuesta trivial, pero me parece que la pregunta no es obviamente tan difícil como el isomorfismo de grafos, ya que si siempre se puede resolver, no está claro que se pueda modificar el algoritmo para decir si un par arbitrario de grafos es isomorfo. Si no hay una respuesta trivial, entonces mi opinión es que la cuestión es más o menos tan difícil como resolver el problema de P contra NP o el problema de isomorfismo de grafos, pero tal vez no lo sea, ya que se permite asumir respuestas a esos problemas. En cualquier caso, la pregunta se me acaba de ocurrir y todavía no he encontrado una razón para que no me guste, así que aquí está.

Answer 1

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.

Answer 2

Esto no responde directamente a su pregunta, pero arroja luz sobre su dureza computacional.

Su problema es un ejemplo de problemas con las promesas . Si esta variante relacionada con su problema de la promesa no se puede resolver en tiempo polinómico, entonces $P \ne NP$ . Sea $HC$ sea la clase de grafos hamiltonianos.

Promesa HC :

Entrada: par de gráficos $(G_1, G_2)$

Sí: $(G_1,G_2)$ tal que $G_1 \in HC$ y $G_2 \not \in HC$

No hay instancia: $(G_1,G_2)$ tal que $G_1 \not \in HC$ y $G_2 \in HC$

El problema de la promesa de la APS está en $NP \cap coNP$ y NP-completo (bajo reducción de Turing en tiempo polinomial) (Ver Corolario 1 y Teorema 4 en la referencia). Un ciclo hamiltoniano en $G_1$ es el certificado para las instancias Yes y Hamiltonian Cycle en $G_2$ es el certificado de No instancias.

El siguiente problema de promesa de isomorfismo de grafos es $GI$ -duro (bajo reducción de Turing en tiempo polinomial) (Teorema 5 en la referencia):

Promesa GI :

Entrada: Triple de gráficos $(G_1, G_2, G_3)$

Sí-instancia $G_1 \cong G_2$ y $G_1 \not \cong G_3$

No-instancia $G_1 \not \cong G_2$ y $G_1 \cong G_3$

Por último, el problema de su promesa está estrechamente relacionado con disyuntiva $NP$ -pares donde (a diferencia de tu problema de la promesa) tanto el Sí-instancia como el NO-instancia son $NP$ conjuntos. Disjuntos $NP$ -pares $(A,B)$ son $P$ -separable si existe un lenguaje computable en tiempo polinómico $S$ que separa $A$ de $B$ ( $A \subseteq S$ y $B \subseteq \overline {S}$ ). Se sabe que la existencia de $P$ -inseparable $NP$ -pares implican $P \ne NP$ .

Referencia :

Alan Selman, Prometer problemas completos para las clases de complejidad