problema del camino más largo

En teoría de grafos e informática teórica , el problema del camino más largo consiste en encontrar un camino simple de longitud máxima en un grafo dado . Un camino se denomina simple si no tiene vértices repetidos ; su longitud puede medirse por el número de aristas o (en grafos ponderados ) por la suma de los pesos de sus aristas. A diferencia del problema del camino más corto , que puede resolverse en tiempo polinomial en grafos sin ciclos de peso negativo, el problema del camino más largo es NP-difícil , y la versión de decisión del problema, que pregunta si existe un camino de al menos una longitud dada, es NP-completa . Esto significa que el problema de decisión no puede resolverse en tiempo polinomial para grafos arbitrarios a menos que P = NP . También se conocen resultados de mayor dificultad que demuestran que es difícil aproximarlo . Sin embargo, tiene una solución en tiempo lineal para grafos dirigidos acíclicos , lo que tiene importantes aplicaciones en la búsqueda del camino crítico en problemas de planificación.

La NP-dificultad del problema del camino más largo sin ponderación se puede demostrar mediante una reducción del problema del camino hamiltoniano : un grafo G tiene un camino hamiltoniano si y solo si su camino más largo tiene longitud n  −  1, donde n es el número de vértices en G. Dado que el problema del camino hamiltoniano es NP-completo, esta reducción muestra que la versión de decisión del problema del camino más largo también es NP-completa. En este problema de decisión, la entrada es un grafo G y un número k ; la salida deseada es sí si G contiene un camino de k o más aristas, y no en caso contrario. ^{[ 1 ]}

Si el problema del camino más largo pudiera resolverse en tiempo polinomial, podría utilizarse para resolver este problema de decisión, encontrando el camino más largo y comparando su longitud con el número k . Por lo tanto, el problema del camino más largo es NP-difícil. La pregunta "¿existe un camino simple en un grafo dado con al menos k aristas?" es NP-completa. ^{[ 2 ]} 

En grafos completos ponderados con pesos de aristas no negativos, el problema del camino más largo ponderado es el mismo que el problema del camino del viajante , porque el camino más largo siempre incluye todos los vértices. ^{[ 3 ]}

El camino más largo entre dos vértices dados s y t en un grafo ponderado G es lo mismo que el camino más corto en un grafo −G derivado de G cambiando cada peso por su negación. Por lo tanto, si se pueden encontrar caminos más cortos en −G ^, entonces también se pueden encontrar caminos más largos en G. [ ^{4 ]}

Para la mayoría de los grafos, esta transformación no es útil porque crea ciclos de longitud negativa en − G . Pero si G es un grafo acíclico dirigido (DAG), entonces no se pueden crear ciclos negativos, y se puede encontrar un camino más largo en G en tiempo lineal aplicando un algoritmo de tiempo lineal para caminos más cortos en − G , que también es un grafo acíclico dirigido. ^{[ 4 ]} Para un DAG, el camino más largo desde un vértice de origen a todos los demás vértices se puede obtener ejecutando el algoritmo de camino más corto en − G .

De manera similar, para cada vértice v en un DAG dado, la longitud del camino más largo que termina en v se puede obtener mediante los siguientes pasos:

1. Encuentra un orden topológico del DAG dado.
2. Para cada vértice v del DAG, en el orden topológico, calcule la longitud del camino más largo que termina en v , considerando sus vecinos entrantes y sumando uno a la longitud máxima registrada para dichos vecinos. Si v no tiene vecinos entrantes, establezca la longitud del camino más largo que termina en v en cero. En ambos casos, registre este valor para que los pasos posteriores del algoritmo puedan acceder a él.

Una vez hecho esto, se puede obtener el camino más largo en todo el DAG comenzando en el vértice v con el mayor valor registrado, luego retrocediendo repetidamente hasta su vecino entrante con el mayor valor registrado e invirtiendo la secuencia de vértices encontrados de esta manera.

Esto es equivalente a ejecutar el algoritmo de ruta más corta en − G .

Björklund, Husfeldt y Khanna (2004) escriben que el problema del camino más largo en grafos no dirigidos no ponderados "es conocido por la dificultad de entender su dureza de aproximación". ^{[ 6 ]} El mejor algoritmo de aproximación en tiempo polinomial conocido para este caso logra solo una razón de aproximación muy débil,${\displaystyle n/\exp(\Omega ({\sqrt {\log n}}))}$. ^{[ 7 ]} Para todos${\displaystyle \epsilon >0}$, no es posible aproximar el camino más largo con un factor de${\displaystyle 2^{(\log n)^{1-\epsilon }}}$a menos que NP esté contenido dentro de un tiempo determinista cuasipolinomial ; sin embargo, existe una gran brecha entre este resultado de inaproximabilidad y los algoritmos de aproximación conocidos para este problema. ^{[ 8 ]}

En el caso de grafos dirigidos pero no ponderados, se conocen resultados de inaproximabilidad fuertes. Para cada${\displaystyle \epsilon >0}$El problema no se puede aproximar con un factor de${\displaystyle n^{1-\epsilon }}$a menos que P = NP, y con supuestos más fuertes de la teoría de la complejidad no se puede aproximar dentro de un factor de${\displaystyle n/\log ^{2+\epsilon }n}$. ^{[ 6 ]} La técnica de codificación por colores se puede utilizar para encontrar caminos de longitud logarítmica, si existen, pero esto da una relación de aproximación de solo${\displaystyle O(n/\log n)}$. ^{[ 9 ]}

El problema del camino más largo es tratable con parámetros fijos cuando se parametriza por la longitud del camino. Por ejemplo, se puede resolver en un tiempo lineal con respecto al tamaño del grafo de entrada (pero exponencial con respecto a la longitud del camino), mediante un algoritmo que realiza los siguientes pasos:

1. Realizar una búsqueda en profundidad del grafo.${\displaystyle d}$sea ​​la altura del árbol de búsqueda en profundidad resultante .
2. Utilice la secuencia de caminos de raíz a hoja del árbol de búsqueda en profundidad, en el orden en que fueron recorridos por la búsqueda, para construir una descomposición de caminos del grafo, con ancho de camino${\displaystyle d}$.
3. Aplique programación dinámica a esta descomposición de caminos para encontrar el camino más largo en tiempo${\displaystyle O(d!2^{d}n)}$, dónde${\displaystyle n}$es el número de vértices en el grafo.

Dado que la ruta de salida tiene una longitud al menos tan grande como${\displaystyle d}$, el tiempo de ejecución también está limitado por${\displaystyle O(\ell !2^{\ell }n)}$, dónde${\displaystyle \ell }$es la longitud del camino más largo. ^{[ 10 ]} Usando codificación de colores, la dependencia de la longitud del camino se puede reducir a una exponencial simple. ^{[ 9 ] [ 11 ] [ 12 ] [ 13 ]} Una técnica de programación dinámica similar muestra que el problema del camino más largo también es tratable con parámetros fijos cuando se parametriza por el ancho del árbol del grafo.

Para grafos con ancho de clique acotado , el camino más largo también se puede resolver mediante un algoritmo de programación dinámica de tiempo polinomial. Sin embargo, el exponente del polinomio depende del ancho de clique del grafo, por lo que este algoritmo no es tratable con parámetros fijos. El problema del camino más largo, parametrizado por el ancho de clique, es difícil para la clase de complejidad parametrizada.${\displaystyle W[1]}$, lo que demuestra que es improbable que exista un algoritmo tratable con parámetros fijos. ^{[ 14 ]}

Un algoritmo de tiempo lineal para encontrar el camino más largo en un árbol fue propuesto por Edsger Dijkstra alrededor de 1960, mientras que una demostración formal de este algoritmo se publicó en 2002. ^{[ 15 ]} Además, un camino más largo puede calcularse en tiempo polinomial en árboles ponderados, en grafos de bloques , en cactus , ^{[ 16 ]} en grafos de permutación bipartitos , ^{[ 17 ]} y en grafos ptolemaicos . ^{[ 18 ]}

Para la clase de gráficos de intervalos , un${\displaystyle O(n^{4})}$Se conoce un algoritmo de tiempo polinomial que utiliza un enfoque de programación dinámica. ^{[ 19 ]} Este enfoque de programación dinámica se ha explotado para obtener algoritmos de tiempo polinomial en las clases más amplias de grafos de arcos circulares ^{[ 20 ]} y de grafos de cocomparabilidad (es decir, de los complementos de los grafos de comparabilidad , que también contienen grafos de permutación ), ^{[ 21 ]} ambos con el mismo tiempo de ejecución.${\displaystyle O(n^{4})}$. Este último algoritmo se basa en propiedades especiales del ordenamiento de vértices de búsqueda en profundidad lexicográfica (LDFS) ^{[ 22 ]} de grafos de cocomparabilidad. Para los grafos de cocomparabilidad también existe un algoritmo alternativo de tiempo polinomial con mayor tiempo de ejecución.${\displaystyle O(n^{7})}$es conocido, que se basa en el diagrama de Hasse del conjunto parcialmente ordenado definido por el complemento del grafo de co-comparabilidad de entrada. ^{[ 23 ]}

Además, el problema del camino más largo se puede resolver en tiempo polinomial en cualquier clase de grafos con ancho de árbol o ancho de clique acotado, como los grafos hereditarios de distancia . Finalmente, es claramente NP-difícil en todas las clases de grafos en las que el problema del camino hamiltoniano es NP-difícil, como en los grafos divididos , los grafos circulares y los grafos planares .

Un modelo simple de un grafo dirigido acíclico es el modelo de Price , desarrollado por Derek J. de Solla Price para representar redes de citas . Este es lo suficientemente simple como para permitir encontrar resultados analíticos para algunas propiedades. Por ejemplo, la longitud del camino más largo, desde el n-ésimo nodo agregado a la red hasta el primer nodo de la red, escala como ^{[ 24 ].}${\displaystyle \ln(n)}$.

• Teorema de Gallai-Hasse-Roy-Vitaver , una relación de dualidad entre caminos más largos y coloración de grafos.
• El camino del caballero más largo sin cruzar
• Serpiente en la caja , el camino inducido más largo en un grafo hipercubo
• El modelo de Price , un modelo simple de red de citas donde las longitudes de ruta más largas se pueden encontrar analíticamente.

• " Encuentra el camino más largo ", canción de Dan Barrett