El ciclo más largo contenido en dos ciclos.

¿Está el siguiente problema NP-completo? (Asumo que sí).

Entrada: un gráfico no dirigido en el que el conjunto de bordes puede descomponerse en dos ciclos simples separados por bordes (estos no son parte de la entrada).$k \in \mathbb{N},G=(V,E)$

Pregunta: ¿Hay un ciclo simple en $G$ con una longitud mayor que $k$ ?

Obviamente, el problema está en NP y el grado máximo en $G$ es $\leq 4$ , pero eso no parece ayudar.

Un intento de reducción ...

Reducción de la ruta hamiltoniana en el dígrafo con un grado máximo 3 que es NPC [G&J]$G = (V,E)$

• ignore la dirección de los bordes y, utilizando un primer escaneo de profundidad (no dirigido) desde un nodo arbitrario, divida los bordes de en dos conjuntos de caminos distintos (no dirigidos) (rojo y verde en las figuras);$G$
• unirse a los caminos rojos agregando "nodos de enlace" adicionales (nodos morados en la figura B) y hacer un circuito rojo no dirigido; unirse a los caminos verdes agregando "nodos de enlace" adicionales (nodos morados en la figura) y hacer un circuito verde no dirigido;
• transformar cada nodo original de grado 1 y grado 2 (figura C), agregando nodos amarillos en el borde rojo de entrada , y agregando nodos amarillos en el primer borde rojo de salida ; finalmente agregue nodos amarillos "hacia" el segundo borde verde de salida usando una ruta "envuelta" alrededor de que toque los nodos amarillos más exteriores de los bordes rojos (figura D).$b \in V$$k$$a\to b$$k$$b \to c$$k$$b \to d$$b$

En el gráfico resultante, todos los nodos amarillos pueden atravesarse por una ruta simple solo de las dos formas mostradas en la figura E y la figura F, que corresponden a los dos recorridos válidos del nodo original ; informalmente, si se usa un borde hacia el nodo púrpura de "enlace" adicional, no se pueden atravesar nodos amarillos.$3k$$b \in V$$k$

• Transforme cada nodo original de V de grado 2 y grado 1 de manera similar

Elegir un lo suficientemente grande, el gráfico de resultados tiene una ruta simple de longitud mayor que si y solo si el gráfico original tiene una ruta hamiltoniana (de longitud )$k \gg |V|$$G'$$3k(|V|-1)$$G$$|V|-1$

La imagen más grande se puede descargar aquí.

Inspirado por la respuesta de Vor, quiero dar una más simple.

Comience con el problema del ciclo hamiltoniano para el problema de los gráficos de cuadrícula, que fue probado por Itai.

Se puede ver fácilmente que el conjunto de bordes de un gráfico de cuadrícula se puede dividir en 2 subconjuntos disjuntos: horizontal y vertical.

Entonces, ahora tenemos que tejer todos los horizontales en un ciclo simple, y tejer todos los verticales en otro ciclo simple.

Esta es una tarea muy fácil: para las verticales, barra de izquierda a derecha, simplemente conecte los espacios verticales, luego conecte la línea vertical coordinada x consecutiva, luego conecte el vértice inferior izquierdo con el vértice superior derecho. Haz lo mismo para los bordes horizontales.

Tenga en cuenta que el gráfico obtenido sigue siendo simple, no dirigido y satisface los requisitos. Es simple porque en los últimos pasos de la fase vertical y la fase horizontal, tratamos con dos pares de vértices diferentes.

Ahora, haz un truco similar al que hizo Vor. En cada vértice, para cada uno de sus bordes incidentes originales, agregue nuevos vértices. Como de costumbre, ahouls sea lo suficientemente grande. Por último, la duración de un ciclo hamiltoniano genuino debería ser. Pero, por supuesto, no es hamiltoniano del gráfico obtenido.$k$$k$$2k|V|$