Hamiltonicidad de gráficos k-regulares

Se sabe que es NP completo para probar si existe un ciclo hamiltoniano en un gráfico de 3 regulares, incluso si es plano (Garey, Johnson y Tarjan, SIAM J. Comput. 1976) o bipartito (Akiyama, Nishizeki, y Saito, J. Inform. Proc. 1980) o para probar si existe un ciclo hamiltoniano en un gráfico 4-regular, incluso cuando es el gráfico formado por una disposición de curvas de Jordan (Iwamoto y Toussaint, IPL 1994).

¿Para qué otra k se sabe que tiene NP completo para probar la Hamiltonicidad de los gráficos k-regulares?

El caso particular que me interesa son los gráficos de 6 regulares, con la condición adicional de que el gráfico tenga un número impar de vértices. Si se pudiera demostrar que este caso es NP-completo (o polinomial), tendría un impacto en un problema de dibujo gráfico descrito en http://arxiv.org/abs/1009.0579 . La condición de "número impar de vértices" se debe a que lo que realmente quiero saber es, para las gráficas de 6 regulares, si la gráfica contiene un ciclo hamiltoniano o un factor bipartito de 2; pero tener un número impar de vértices elimina la posibilidad de un factor bipartito de 2, dejando solo la posibilidad de un ciclo hamiltoniano.

Primer paso, supongamos que el gráfico tiene un número par de vértices. En la segunda etapa, ampliaremos la construcción, de modo que si k es par, entonces mostraremos cómo convertir el gráfico en un número impar de vértices.

La solución es un refinamiento de la idea sugerida en la otra respuesta.

Primera parte

Reclamación: Dado un gráfico G regular con un número par de vértices, se puede calcular un gráfico H que es ( k + 1 ) regular, y H es hamiltoniano si G es hamiltoniano.$k$$G$$H$$(k+1)$$H$$G$

$k$$G$$G_1$$G_2$$v \in V(G)$$v_1$$v_2$$k+2$$v$$v'$v 1 v ′ v 2 v ″ C ( v ) $v''$$v_1$$v'$$v_2$$v''$. Deje denotar este componente para .$C(v)$$v$

Repita esto para todos los vértices de y deje que denote el gráfico resultante.$G$$H$

Claramente, el gráfico es regular. Afirmamos que es hamiltoniano si y solo si es hamiltoniano.k + 1 H $H$$k+1$$H$$G$

Una dirección es clara. Teniendo en cuenta un ciclo Hambiltonian en , podemos traducirlo en un ciclo en el . De hecho, cada vez que el ciclo visita un vértice , lo interpretamos como un movimiento de a (o viceversa) mientras visitamos todos los vértices en . Como tal, esto resulta en un ciclo de Hamilton en . (Tenga en cuenta que aquí es donde estamos usando el hecho de que el número original de vértices es par; si el ciclo es impar, esto se rompe).H v v 1 v 2 C ( v ) $G$$H$$v$$v_1$$v_2$$C(v)$$H$

En cuanto a la otra dirección, considere un ciclo de Hamilton en . Debe ser que es visitada por una parte del ciclo que comienza en , visita todos los vértices de y parte de (o la opción simétrica). De hecho, el ciclo hamiltoniano no puede entrar y salir del mismo . Como tal, un ciclo de Hamilton en como una interpretación natural como un ciclo de Hamilton en . QEDC ( v ) v 1 C ( v ) v 2 v i H $H$$C(v)$$v_1$$C(v)$$v_2$$v_i$$H$$G$

Segunda parte

Como se señala a continuación por Tsuyoshi, cualquier gráfico de 3 regulares tiene un número par de vértices. Como tal, el problema es difícil para un gráfico regular de con un número par de vértices. Es decir, la reducción anterior muestra que el problema es difícil para cualquier gráfico regular, aunque el gráfico resultante tiene un número par de vértices.$3$$k$

Observamos que esto implica que el siguiente problema es NP-hard.

Problema A: Decidir si un gráfico k-regular con un número par de vértices tiene un ciclo hamiltoniano que atraviesa un borde específico .$G$$e$

Sin embargo, si es incluso entonces dado una instancia podemos reducirlo al problema deseado. De hecho, reemplazamos el borde por una camarilla de vértices, como antes de eliminar un borde en la camarilla, y conectar sus dos puntos finales a los puntos finales de , y eliminar del gráfico. Claramente, para el nuevo gráfico :( G , e ) e k + 1 e e $k$$(G, e)$$e$$k+1$$e$$e$$H$

• $H$ es -regular.$k$
• G $H$ es hamiltoniano si y sólo si es hamiltoniano con un ciclo de uso de .$G$$e$
• | V ( G ) | + k + 1 $H$ tiene vértices => tiene un número impar de vértices.$|V(G)| + k+1$$H$

Tenga en cuenta que un gráfico regular, para impar, debe tener un número par de vértices (solo cuente los bordes). Como tal, no hay gráficos regulares con un número impar de vértices, siendo impar.k k $k$$k$$k$$k$

Resultado

NP-Hard es decidir si un gráfico regular tiene un ciclo hamiltoniano para . El problema sigue siendo NP-Hard incluso si el gráfico tiene un número impar de vértices.k ≥ $k$$k\geq 3$

Por supuesto, siempre es posible que haya cometido un error estúpido ...

Ejercicio

Si queremos pasar de una gráfica que es regular a una gráfica que es (digamos) regular entonces la gráfica resultante de aplicar la reducción anterior repetidamente da como resultado una gráfica con un tamaño que depende exponencialmente de . Demuestre que, dado un gráfico regular e , se puede construir un gráfico que sea regular y su tamaño sea polinomial en y , donde es el número de vértices de . Además, es hamiltoniano si y solo si es hamiltoniano.2 k k k G i > 2 H ( k + i ) k , i n n G G $k$$2k$$k$$k$$G$$i >2$$H$$(k+i)$$k,i$$n$$n$$G$$G$$H$

(Estoy publicando esto como un ejercicio, no como una pregunta, ya que sé cómo resolverlo).

EDITAR: Esta prueba es incorrecta, como se señala en los comentarios. (¿Debo eliminar la publicación?)

Se siente intuitivamente como si Hamiltonicity es NP-hard para gráficos k-regulares, entonces también debería ser NP-hard para gráficos regulares (k + 1). Aquí hay una reducción al final del sobre, que me parece bien, pero por supuesto podría haber un error.

Deje que G sea un gráfico k-regular. Deje que G 'sea el producto cartesiano gráfico de G y una arista. En otras palabras, G 'es el gráfico que tiene dos copias de G, y cada vértice está conectado a su copia. G 'ahora es (k + 1) regular, ya que cada vértice tiene 1 borde extra.

Reclamación: G tiene un ciclo hamiltoniano si y solo si G 'tiene un ciclo hamiltoniano.

Prueba: si G tiene un ciclo hamiltoniano, es fácil ver que G 'también tiene uno. Digamos que (u, v) es una ventaja en el ciclo hamiltoniano. Recorre el ciclo de u a v sin usar ese borde, y ahora en lugar de usar el borde, ve a v 'desde v, donde v' es el vértice correspondiente a v en la copia de G. Ahora recorre el ciclo en orden inverso en este gráfico, que nos llevará de vuelta a usted '. Ahora ve de u 'a u, que completa el ciclo.

Si G 'tiene un ciclo hamiltoniano que comienza desde el vértice u, considere la misma secuencia de recorridos en G. Cada vez que se realiza un movimiento a un vértice adyacente en el mismo gráfico, hacemos el mismo movimiento en G. Cada vez que se realiza un movimiento al vértice correspondiente en el otro gráfico, no hacemos nada. Como cada movimiento es válido en el gráfico G y el ciclo termina en el vértice u, este es un ciclo hamiltoniano.