Clases de gráficos con ciclo Hamiltoniano fácil pero TSP NP-duro

13

El problema del ciclo hamiltoniano (HC) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico no dirigido dado. El problema del vendedor ambulante (TSP) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico ponderado de borde dado y minimice la distancia total medida por la suma de los pesos de los bordes en el ciclo. HC es un caso especial de TSP, y se sabe que ambos son NP completos [Garey & Johnson]. (Consulte los enlaces anteriores para obtener más detalles y variantes de estos problemas).

¿Hay clases de gráficos estudiados en los que el problema del ciclo de Hamilton se pueda resolver en tiempo polinómico mediante un algoritmo no trivial , pero el problema del vendedor ambulante es NP-difícil?

No trivial es excluir clases como la clase de gráficos completos, donde se garantiza que existe un ciclo hamiltoniano y se puede encontrar fácilmente, o generalmente clases de gráficos donde siempre se garantiza que existe un HC.

cc.complexity-theory np-hardness hamiltonian-paths tsp graph-classes Standa Zivny
fuente

Respuestas:

20

Los cogramas no siempre son hamiltonianos, tienen pruebas de tiempo polinomial para Hamiltonicity y son NP difíciles de resolver para el problema del vendedor ambulante.

De manera más general, el problema del ciclo de Hamilton puede resolverse en tiempo polinómico (pero no es de parámetros fijos tratables) en gráficos de ancho de camarilla acotado ; véase, por ejemplo, Fomin et al., "Ancho de camarilla: sobre el precio de la generalidad", SODA'09. Pero una vez más, porque estas familias de gráficos incluyen los gráficos completos, el TSP es difícil en estos gráficos.

David Eppstein
fuente
Tengo curiosidad por tu última declaración. ¿Se debe a que el recorrido TSP identificaría efectivamente a las camarillas haciendo que todos los vértices de las camarillas sean contiguos en el recorrido?
Suresh Venkat
1
No, quiero decir simplemente que TSP es difícil incluso en un gráfico completo, y los gráficos completos se encuentran entre los gráficos con ancho de camarilla acotado. Los gráficos completos en sí mismos no brindan una buena respuesta a la pregunta porque Hamiltonicity es trivial para ellos, pero las superclases de las camarillas (como los cogramas) pueden tener pruebas de Hamiltonicity no triviales pero polinomiales.
David Eppstein
11

¿Qué tal gráficos completos ? Dado que TSP siempre se puede reducir a una instancia en gráficos completos (agregando distancias apropiadas entre los no bordes), todavía es NP-difícil resolver TSP en gráficos completos. Pero cualquier gráfico completo es hamiltoniano.

Hsien-Chih Chang 張顯 之
fuente
¡Sí, por supuesto, muchas gracias! Se olvidó de excluir gráficos completos, y para el caso, todas las clases de gráficos donde HC es solucionable trivialmente.
Standa Zivny
3
@Standa Zivny: No estoy seguro de si va a editar la pregunta o no, pero si desea excluir "todas las clases de gráficos donde HC tiene solución trivial", debe editar la pregunta. Sin embargo, dudo que sea posible formular la distinción entre el caso en que HC se puede resolver "fácilmente" y el caso en que HC se puede resolver "trivialmente".
Tsuyoshi Ito
@ Tsuyoshi Ito: Un buen punto, he editado la pregunta.
Standa Zivny
@StandaZivny: no todos los gráficos triviales para HC son difíciles para TSP, por ejemplo, gráficos de ruta.
RB
3

Hay muchas clases infinitas de gráficos que se sabe que tienen circuitos hamiltonianos. Dos clases especialmente interesantes son los n-cubos y los gráficos de Halin. Una forma de pensar en los gráficos de Halin es incrustar un árbol con al menos 3 vértices y que no tenga vértices de valencia dos en el plano, y luego pasar un circuito simple a través de los vértices de 1 valente del árbol.

http://en.wikipedia.org/wiki/Halin_graph

Se sabe que estos gráficos tienen un HC y, de hecho, son pancíclicos (circuitos de todas las longitudes) o carecen exactamente de una longitud de circuito que debe ser de longitud uniforme.

Joseph Malkevitch
fuente