El problema del camino más largo es NP-hard. La prueba (¿típica?) Se basa en una reducción del problema del camino hamiltoniano (que es NP completo). Tenga en cuenta que aquí la ruta se considera simple (nodo). Es decir, ningún vértice puede ocurrir más de una vez en el camino. Obviamente, también es simple de borde (no ocurrirá ningún borde más de una vez en el camino).
Entonces, ¿qué pasa si abandonamos el requisito de encontrar una ruta simple (nodo) y nos limitamos a encontrar una ruta simple (borde)? A primera vista, dado que encontrar un camino euleriano es mucho más fácil que encontrar un camino hamiltoniano, uno podría tener la esperanza de que encontrar el camino más largo sería más fácil que encontrar el camino más largo. Sin embargo, no puedo encontrar ninguna referencia que lo pruebe, y mucho menos una que proporcione un algoritmo.
Tenga en cuenta que estoy al tanto del argumento hecho aquí: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph Sin embargo, el argumento parece defectuoso en su forma actual, ya que básicamente muestra que podría resolver el caso simple de borde resolviendo el caso simple de nodo en un gráfico diferente (por lo que la reducción es al revés). No está claro que la reducción pueda cambiarse fácilmente para que funcione de otra manera también. (Aún así, muestra que al menos el problema de los senderos más largos no es más difícil que el problema de los caminos más largos).
Entonces, ¿hay algún resultado conocido para encontrar senderos más largos (caminos de borde simple)? Complejidad (clase)? Algoritmo (eficiente)?
Respuestas:
A partir de los comentarios anteriores: el problema del ciclo de Hamilton sigue siendo NP completo incluso en gráficos de cuadrícula con un grado máximo 3 [1], pero en estos gráficos cada recorrido de un nodo requiere dos bordes y, como máximo, un borde permanece sin usar, por lo que no se puede utilizar un nodo atravesado dos veces por un camino euleriano.
Entonces, aparentemente hay una reducción inmediata del problema del ciclo de Hamilton a su problema: dado un gráfico de cuadrícula con un grado máximo 3 , solo solicite un rastro de longitud | V | .G = ( V, E) El | VEl |
Pero se pueden usar los tres bordes del nodo al final del camino; Para evitar esta situación, puede elegir el nodo superior izquierdo del gráfico de cuadrícula (que tiene grado dos) y agregar dos nodos: V ′ = V ∪ { u ′ , u ″ } y una nueva arista E = E ∪ { ( u , u ′ ) , ( u , u ″ ) } y solicite un rastro de longitud | V ′ | = | V | +tu V′= V∪ { u′, u′ ′} mi= E∪ { ( u , u′) , ( u , u′ ′) } : informalmente, el borde agregado obliga a u ′ , u ″ a ser los puntos finales del camino.El | V′El | = | VEl | +2 tu′, u′ ′
[1] Christos H Papadimitriou, Umesh V Vazirani, Sobre dos problemas geométricos relacionados con el problema del vendedor ambulante, Journal of Algorithms, Volumen 5, Número 2, junio de 1984, páginas 231-246, ISSN 0196-6774
fuente