Problema del camino más largo

Problema de encontrar la ruta simple más larga para un gráfico dado

En teoría de grafos y ciencias de la computación teóricas , el problema de la ruta más larga es el problema de encontrar una ruta simple de longitud máxima en un grafo dado . Una ruta se llama simple si no tiene vértices repetidos ; la longitud de una ruta puede medirse por su número de aristas o (en grafos ponderados ) por la suma de los pesos de sus aristas. A diferencia del problema de la ruta más corta , que se puede resolver en tiempo polinomial en grafos sin ciclos de peso negativo, el problema de la ruta más larga es NP-duro y la versión de decisión del problema, que pregunta si existe una ruta de al menos una longitud dada, es NP-completa . Esto significa que el problema de decisión no se puede resolver en tiempo polinomial para grafos arbitrarios a menos que P = NP . También se conocen resultados de dureza más fuertes que muestran que es difícil de aproximar . Sin embargo, tiene una solución de tiempo lineal para grafos acíclicos dirigidos , lo que tiene aplicaciones importantes en la búsqueda de la ruta crítica en problemas de programación.

Dureza NP

La NP-dureza del problema de la ruta más larga no ponderada se puede mostrar usando una reducción del problema de la ruta hamiltoniana : un grafo G tiene una ruta hamiltoniana si y solo si su ruta más larga tiene una longitud n  − 1, donde n es el número de vértices en G. Debido a que el problema de la ruta hamiltoniana es NP-completo, esta reducción muestra que la versión de decisión del problema de la ruta más larga 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 una ruta de k o más aristas, y no en caso contrario. ^[1]

Si el problema de la ruta más larga se pudiera resolver en tiempo polinomial, se podría utilizar para resolver este problema de decisión, encontrando una ruta más larga y luego comparando su longitud con el número  k . Por lo tanto, el problema de la ruta más larga es NP-completo. La pregunta "¿existe una ruta simple en un grafo dado con al menos k aristas?" es NP-completa. ^[2]

En gráficos completos ponderados con pesos de aristas no negativos, el problema de la ruta más larga ponderada es el mismo que el problema de la ruta del viajante , porque la ruta más larga siempre incluye todos los vértices. ^[3]

Grafos acíclicos

Un camino más largo entre dos vértices dados s y t en un grafo ponderado G es lo mismo que un camino más corto en un grafo − G derivado de G cambiando cada peso por su negación. Por lo tanto, si los caminos más cortos se pueden encontrar en − G , entonces los caminos más largos también se pueden encontrar 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 una ruta más larga en G en tiempo lineal aplicando un algoritmo de tiempo lineal para rutas más cortas en − G , que también es un grafo acíclico dirigido. ^[4] Para un DAG, la ruta más larga desde un vértice de origen a todos los demás vértices se puede obtener ejecutando el algoritmo de ruta más corta 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. Encuentre un ordenamiento topológico del DAG dado.
2. Para cada vértice v del DAG, en el ordenamiento topológico, calcule la longitud de la ruta más larga que termina en v observando sus vecinos entrantes y sumando uno a la longitud máxima registrada para esos vecinos. Si v no tiene vecinos entrantes, establezca la longitud de la ruta más larga que termina en v en cero. En cualquier caso, registre este número para que los pasos posteriores del algoritmo puedan acceder a él.

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

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

Caminos críticos

El método de la ruta crítica para programar un conjunto de actividades implica la construcción de un gráfico acíclico dirigido en el que los vértices representan los hitos del proyecto y las aristas representan las actividades que deben realizarse después de un hito y antes de otro; cada arista se pondera con una estimación del tiempo que tomará completar la actividad correspondiente. En un gráfico de este tipo, la ruta más larga desde el primer hito hasta el último es la ruta crítica, que describe el tiempo total para completar el proyecto. ^[4]

Los caminos más largos de los gráficos acíclicos dirigidos también se pueden aplicar en el dibujo de gráficos en capas : asignar cada vértice v de un gráfico acíclico dirigido G a la capa cuyo número es la longitud del camino más largo que termina en v da como resultado una asignación de capa para G con el mínimo número posible de capas. ^[5]

Aproximación

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

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

Complejidad parametrizada

El problema de la ruta más larga se puede resolver con parámetros fijos cuando se parametriza por la longitud de la ruta. Por ejemplo, se puede resolver en tiempo lineal en el tamaño del gráfico de entrada (pero exponencial en la longitud de la ruta), mediante un algoritmo que realiza los siguientes pasos:

1. Realizar una búsqueda en profundidad del grafo. Sea la profundidad del árbol de búsqueda en profundidad resultante . ${\displaystyle d}$
2. Utilice la secuencia de rutas de raíz a hoja del árbol de búsqueda en profundidad, en el orden en el que fueron recorridas por la búsqueda, para construir una descomposición de ruta del gráfico, con ancho de ruta . ${\displaystyle d}$
3. Aplique programación dinámica a esta descomposición de ruta para encontrar la ruta más larga en el tiempo , donde es el número de vértices en el gráfico. ${\displaystyle O(d!2^{d}n)}$ ${\displaystyle n}$

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

Para gráficos con un 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 gráfico, por lo que este algoritmo no es manejable 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 , lo que demuestra que es poco probable que exista un algoritmo manejable con parámetros fijos. ^[14] ${\displaystyle W[1]}$

Clases especiales de gráficos

Edsger Dijkstra propuso un algoritmo de tiempo lineal para encontrar el camino más largo en un árbol alrededor de 1960, mientras que una prueba formal de este algoritmo se publicó en 2002. ^[15] Además, se puede calcular un camino más largo en tiempo polinomial en árboles ponderados, en gráficos de bloques , en cactus , ^[16] en gráficos de permutación bipartita , ^[17] y en gráficos ptolemaicos . ^[18]

Para la clase de grafos de intervalo , 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 mayores de grafos de arco circular ^[20] y de grafos de co-comparabilidad (es decir, de los complementos de grafos de comparabilidad , que también contienen grafos de permutación ), ^[21] ambos con el mismo tiempo de ejecución . El último algoritmo se basa en propiedades especiales del ordenamiento de vértices de búsqueda en profundidad lexicográfica (LDFS) ^[22] de grafos de co-comparabilidad. Para grafos de co-comparabilidad también se conoce un algoritmo de tiempo polinomial alternativo con mayor tiempo de ejecución , que se basa en el diagrama de Hasse del conjunto parcialmente ordenado definido por el complemento del grafo de co-comparabilidad de entrada. ^[23] ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{7})}$

Además, el problema de la ruta más larga se puede resolver en tiempo polinomial en cualquier clase de grafos con ancho de árbol acotado o ancho de camarilla acotado, como los grafos hereditarios de distancia . Finalmente, es claramente NP-hard en todas las clases de grafos en las que el problema de la ruta hamiltoniana es NP-hard, como en grafos divididos , grafos circulares y grafos planares .

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

Véase también

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

Referencias

1. Schrijver, Alexander (2003), Optimización combinatoria: poliedros y eficiencia, Volumen 1, Algoritmos y combinatoria, vol. 24, Springer, pág. 114, ISBN 9783540443896.
2. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos (2ª ed.), MIT Press, pág. 978, ISBN 9780262032933.
3. Lawler, Eugene L. (2001), Optimización combinatoria: redes y matroides, Courier Dover Publications, pág. 64, ISBN 9780486414539.
4. Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algoritmos (4.ª ed.), Addison-Wesley Professional, págs. 661–666, ISBN 9780321573513.
5. Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), "Dibujos en capas de dígrafos", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 265–302, ISBN 978-0-13-301615-4.
6. Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev (2004), "Aproximación de ciclos y rutas dirigidas más largas", Proc. Int. Coll. Autómatas, lenguajes y programación (ICALP 2004) , Lecture Notes in Computer Science , vol. 3142, Berlín: Springer-Verlag, págs. 222–233, MR  2160935.
7. Gabow, Harold N .; Nie, Shuxin (2008), "Encontrar caminos largos, ciclos y circuitos", Simposio internacional sobre algoritmos y computación , Lecture Notes in Computer Science, vol. 5369, Berlín: Springer, págs. 752–763, doi :10.1007/978-3-540-92182-0_66, ISBN 978-3-540-92181-3, Sr.  2539968. Para trabajos anteriores con límites de aproximación aún más débiles, véase Gabow, Harold N. (2007), "Finding paths and cycles of superpolylogarithmic length" (PDF) , SIAM Journal on Computing , 36 (6): 1648–1671, doi :10.1137/S0097539704445366, MR  2299418y Björklund, Andreas; Husfeldt, Thore (2003), "Encontrar un camino de longitud superlogarítmica", SIAM Journal on Computing , 32 (6): 1395–1402, doi :10.1137/S0097539702416761, MR  2034242.
8. Karger, David ; Motwani, Rajeev ; Ramkumar, GDS (1997), "Sobre la aproximación de la ruta más larga en un gráfico", Algorithmica , 18 (1): 82–98, doi :10.1007/BF02523689, MR  1432030, S2CID  3241830.
9. Alon, Noga ; Yuster, Raphael; Zwick, Uri (1995), "Codificación de colores", Journal of the ACM , 42 (4): 844–856, doi : 10.1145/210332.210337 , MR  1411787, S2CID  208936467.
10. Bodlaender, Hans L. (1993), "Sobre pruebas menores de tiempo lineal con búsqueda en profundidad", Journal of Algorithms , 14 (1): 1–23, doi :10.1006/jagm.1993.1001, MR  1199244. Para un algoritmo FPT anterior con una dependencia ligeramente mejor de la longitud de la ruta, pero una dependencia peor del tamaño del gráfico, véase Monien, B. (1985), "How to find long paths efficient", Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud., vol. 109, Amsterdam: North-Holland, pp. 239–254, doi :10.1016/S0304-0208(08)73110-4, ISBN 9780444876997, Sr.  0808004.
11. Chen, Jianer; Lu, Songjian; Sze, Sing-Hoi; Zhang, Fenghui (2007), "Algoritmos mejorados para problemas de rutas, coincidencias y empaquetamiento", Proc. 18.° Simposio ACM-SIAM sobre algoritmos discretos (SODA '07) (PDF) , págs. 298–307.
12. Koutis, Ioannis (2008), "Algoritmos algebraicos más rápidos para problemas de rutas y empaquetamiento", Coloquio internacional sobre autómatas, lenguajes y programación (PDF) , Lecture Notes in Computer Science, vol. 5125, Berlín: Springer, pp. 575–586, CiteSeerX 10.1.1.141.6899 , doi :10.1007/978-3-540-70575-8_47, ISBN  978-3-540-70574-1, MR  2500302, archivado desde el original (PDF) el 2017-08-09 , consultado el 2013-08-09.
13. Williams, Ryan (2009), "Encontrar caminos de longitud k en tiempo O *(2 ^k )", Information Processing Letters , 109 (6): 315–318, arXiv : 0807.3026 , doi :10.1016/j.ipl.2008.11.004, MR  2493730, S2CID  10295448.
14. Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2009), "Clique-width: on the price of generality", Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09) (PDF) , págs. 825–834, archivado desde el original (PDF) el 2012-10-18 , consultado el 2012-12-01.
15. Bulterman, RW; van der Sommen, FW; Zwaan, G.; Verhoeff, T.; van Gasteren, AJM (2002), "Sobre el cálculo del camino más largo en un árbol", Information Processing Letters , 81 (2): 93–96, doi :10.1016/S0020-0190(01)00198-3.
16. Uehara, Ryuhei; Uno, Yushi (2004), "Algoritmos eficientes para el problema de la ruta más larga", en Fleischer, Rudolf; Trippen, Gerhard (eds.), Algorithms and Computation, 15.º Simposio Internacional, ISAAC 2004, Hong Kong, China, 20-22 de diciembre de 2004, Actas , Lecture Notes in Computer Science, vol. 3341, Springer, págs. 871–883, doi :10.1007/978-3-540-30551-4_74, ISBN 978-3-540-24131-7.
17. Uehara, Ryuhei; Valiente, Gabriel (2007), "Estructura lineal de gráficos de permutación bipartitos y el problema de la ruta más larga", Information Processing Letters , 103 (2): 71–77, CiteSeerX 10.1.1.101.96 , doi :10.1016/j.ipl.2007.02.010 .
18. Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei (2008), "Problemas de ruta más larga en grafos ptolemaicos", IEICE Transactions , 91-D (2): 170–177, doi : 10.1093/ietisy/e91-d.2.170.
19. Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D. (2011), "El problema de la ruta más larga tiene una solución polinómica en gráficos de intervalos", Algorithmica , 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , doi :10.1007/s00453-010-9411-3, S2CID  7577817 .
20. Mertzios, George B.; Bezakova, Ivona (2014), "Cálculo y conteo de las trayectorias más largas en gráficos de arco circular en tiempo polinomial", Discrete Applied Mathematics , 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi :10.1016/j.dam.2012.08.024 .
21. Mertzios, George B.; Corneil, Derek G. (2012), "Un algoritmo polinomial simple para el problema de la ruta más larga en gráficos de co-comparabilidad", SIAM Journal on Discrete Mathematics , 26 (3): 940–963, arXiv : 1004.4560 , doi :10.1137/100793529, S2CID  4645245.
22. Corneil, Derek G.; Krueger, Richard (2008), "Una visión unificada de la búsqueda de grafos", SIAM Journal on Discrete Mathematics , 22 (4): 1259–1276, doi :10.1137/050623498.
23. Ioannidou, Kyriaki; Nikolopoulos, Stavros D. (2011), "El problema del camino más largo es el polinomio en gráficos de comparabilidad" (PDF) , Algorithmica , 65 : 177–205, CiteSeerX 10.1.1.415.9996 , doi :10.1007/s00453-011-9583-5 , S2CID  7271040 .
24. Evans, TS; Calmon, L.; Vasiliauskaite, V. (2020), "El camino más largo en el modelo de precios", Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode :2020NatSR..1010503E, doi :10.1038/s41598-020-67421-8, PMC 7324613 , PMID  32601403 

Enlaces externos

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