Este problema surgió de mi reciente publicación de blog , supongamos que se le da un recorrido TSP, ¿es completo para determinar si es mínimo?
Más precisamente es el siguiente problema NP-complete:
Instancia: dado un gráfico completo G con aristas ponderadas con enteros positivos y un ciclo simple C que visita todos los nodos de G.
Pregunta: ¿Existe un ciclo simple D que visite todos los nodos de G de modo que el peso total de todos los bordes de D en G sea estrictamente menor que el peso total de todos los bordes de C en G?
Un boceto de una posible reducción para demostrar que está completa NP.
Informalmente comienza a partir de una fórmula 3SAT modificada que se usa para mostrar que 3SAT es ASP completo (otro problema de solución) y "sigue" la cadena estándar de reducciones 3SAT => HAMCYCLE DIRECTED => HAMCYCLE UNDIRECTED => TSP
Comience con una fórmula 3SAT con n variables de x 1 , . . . x n y m caluses C 1 , . . . , C m ;φnx1,...xnmC1,...,Cm
Transfórmalo a una nueva fórmula agregando una nueva variable t ...;φ′t
... y expandiendo cada cláusula a ( x i 1 ∨ x i 2 ∨ x i 3 ∨ t ) ;(xi1∨xi2∨xi3)(xi1∨xi2∨xi3∨t)
A partir de construya el gráfico de estructura de diamantes G = { V , E } utilizado para demostrar que el CICLO HAMILTONIANO DIRIGIDO es NP-Completo; supongamos que cada cláusula C j corresponde al nodo N j en G ;φ′G={V,E}CjNjG
Modifique en el gráfico G ′ = { V ′ , E ′ } reemplazando cada nodo u con tres nodos vinculados u 1 , u 2 , u 3 y modifique los bordes de acuerdo con la reducción estándar utilizada para demostrar la integridad de NP del CICLO HAMILTONIANO NO DIRIGIDO del CICLO HAMILTONIANO DIRECTO, es decir, u 1 es el nodo utilizado para los bordes entrantes, u 3 es el nodo utilizado para los bordes salientes;GG′={V′,E′}uu1,u2,u3u1u3
Convierta la instancia de CICLO HAMILTONIANO NO DIRIGIDO en en una instancia de TSP T en la que todos los bordes de G ' tienen peso w = 1 , excepto el borde (único) en el diamante que va a la asignación "positiva" de t que tiene peso w = 2 (borde rojo en la figura a continuación); finalmente los bordes agregados para completar G ' tienen peso w = 3 .G′TG′w=1tw=2G′w=3
Claramente, la instancia TSP tiene un ciclo simple que visita todos los nodos que corresponde a la asignación satisfactoria de φ ′ en la que t = t r u e (y este recorrido se puede construir fácilmente en tiempo polinómico), pero tiene un peso total | V ′ | + 1 (porque usa la arista que corresponde a la asignación t = t r u e que tiene peso 2). T tiene otro ciclo simple que visita todos los nodos con un peso total más bajo | V ′ |Tφ′t=true|V′|+1t=trueT|V′|si y solo si el borde del peso que corresponde a la asignación t = t r u e no se usa; o equivalentemente si y solo si hay otra asignación satisfactoria de φ ′ en la que
t = f a l s e ; pero esto puede ser cierto si y solo si la fórmula original φ es satisfactoria.2t=trueφ′t=falseφ
Lo pensaré más y escribiré una prueba formal (si no resulta estar equivocado :-). Avíseme si necesita más detalles sobre uno o más de los pasajes anteriores.
Como señaló domotorp, una consecuencia interesante es que el siguiente problema es NP-completo: dado un gráfico y una ruta hamiltoniana, ¿ tiene G un ciclo hamiltoniano?GG
Entonces, esencialmente muestra que, dado un gráfico y una ruta H, es NPc decidir si tiene un ciclo H, ¿verdad?
domotorp
Se ve muy bien. Gracias por esforzarse en la redacción. Algunos cambios para abordar directamente mi pregunta: los bordes del gráfico deben ser ponderados 1 a excepción de ese borde especial que debe ser ponderado 2 y los no bordes deben ser ponderados 3.
Papadimitriou y Steiglitz (1977) han demostrado la completitud NP de este problema.
fuente