En teoría de grafos y ciencias de la computación teóricas , el problema del camino más largo es el problema de encontrar un camino simple de máxima longitud en un gráfico dado. Una ruta se llama simple si no tiene vértices repetidos; la longitud de un camino puede medirse por su número de bordes o (en gráficos ponderados ) por la suma de los pesos de sus bordes. En contraste con el problema de la ruta más corta , que se puede resolver en tiempo polinómico en gráficos sin ciclos de peso negativo, el problema de la ruta más larga es NP-hard y la versión de decisión del problema, que pregunta si existe una ruta de al menos algunos dados. longitud, es NP-completo. Esto significa que el problema de decisión no se puede resolver en tiempo polinómico para gráficas arbitrarias 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 gráficos acíclicos dirigidos , que tiene aplicaciones importantes para encontrar la ruta crítica en problemas de programación.
Dureza NP
La dureza NP del problema del camino más largo no ponderado se puede mostrar usando una reducción del problema del camino hamiltoniano : un gráfico G tiene un camino hamiltoniano si y solo si su camino más largo tiene una longitud n - 1, donde n es el número de vértices en G . Debido a que el problema de la ruta de Hamilton 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 gráfico 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 pudiera resolverse en tiempo polinomial, podría usarse 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-hard. La pregunta "¿existe una ruta simple en un gráfico dado con al menos k bordes?" Es NP-completa. [2]
En gráficos completos ponderados con pesos de arista no negativos, el problema de la ruta más larga ponderada es el mismo que el problema de la ruta del vendedor ambulante , porque la ruta más larga siempre incluye todos los vértices. [3]
Gráficos acíclicos
Un camino más largo entre dos vértices dados s y t en un gráfico ponderado G es la misma cosa que un camino más corto en un gráfico - G deriva de G cambiando cada peso a 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 pueden ser encontrados en G . [4]
Para la mayoría de los gráficos, esta transformación no es útil, ya que crea ciclos de longitud negativa en - G . Pero si G es un gráfico acíclico dirigido , 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 gráfico acíclico dirigido. [4] Para un DAG, la trayectoria más larga desde un vértice fuente a todos los demás vértices se puede obtener mediante la ejecución del algoritmo de la 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:
- Encuentre un orden topológico del DAG dado.
- Para cada vértice v del DAG, en el orden topológico, calcule la longitud de la ruta más larga que termina en v observando sus vecinos entrantes y agregando 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 que se encuentran en Por aquí.
Esto es equivalente a ejecutar el algoritmo de ruta más corta en - G .
Caminos críticos
El método de 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 hitos del proyecto y los bordes representan actividades que deben realizarse después de un hito y antes de otro; cada borde está ponderado por una estimación de la cantidad de tiempo que llevará completar la actividad correspondiente. En dicho gráfico, 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]
Las rutas más largas de 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 de la ruta más larga que termina en v da como resultado una asignación de capa para G con el mínimo posible número de capas. [5]
Aproximación
Björklund, Husfeldt y Khanna (2004) escriben que el problema de la trayectoria más larga en gráficos no ponderados no dirigidos "es notorio por la dificultad de comprender su dureza de aproximación". [6] El mejor algoritmo de aproximación de tiempo polinomial conocido para este caso solo logra una relación de aproximación muy débil,. [7] Para todos, no es posible aproximar el camino más largo dentro de un factor de a menos que NP esté contenido en un tiempo determinista cuasi-polinómico ; sin embargo, existe una gran brecha entre este resultado de inaproximación y los algoritmos de aproximación conocidos para este problema. [8]
En el caso de gráficos no ponderados pero dirigidos, se conocen fuertes resultados de inapropiabilidad. Para cada el problema no se puede aproximar a un factor de a menos que P = NP, y con supuestos teóricos de la 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 rutas de longitud logarítmica, si existen, pero esto da una relación de aproximación de solo. [9]
Complejidad parametrizada
El problema de la ruta más larga es tratable 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:
- Realice una búsqueda en profundidad del gráfico. Dejarsea la profundidad del árbol de búsqueda en profundidad resultante .
- Utilice la secuencia de rutas de raíz a hoja del árbol de búsqueda en profundidad, en el orden en que fueron atravesadas por la búsqueda, para construir una descomposición de ruta del gráfico, con ancho de ruta.
- Aplique programación dinámica a esta descomposición de ruta para encontrar la ruta más larga en el tiempo, dónde es el número de vértices del gráfico.
Dado que la ruta de salida tiene una longitud al menos tan grande como , el tiempo de ejecución también está limitado por , dónde es la longitud del camino más largo. [10] Utilizando la codificación de colores, la dependencia de la longitud de la ruta se puede reducir a una sola exponencial. [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 por el ancho de árbol del gráfico.
Para gráficos de ancho de camarilla acotado , la ruta más larga 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 la camarilla del gráfico, por lo que este algoritmo no es manejable con parámetros fijos. El problema de la ruta más larga, parametrizado por el ancho de la camarilla, es difícil para la clase de complejidad parametrizada, lo que muestra que es poco probable que exista un algoritmo manejable de parámetros fijos. [14]
Clases especiales de gráficos
Dijkstra propuso un algoritmo de tiempo lineal para encontrar una ruta más larga en un árbol en la década de 1960, mientras que una prueba formal de este algoritmo se publicó en 2002. [15] Además, una ruta más larga se puede calcular en tiempo polinómico 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 gráficos de intervalo , unSe conoce el algoritmo de tiempo, que utiliza un enfoque de programación dinámica. [19] Este enfoque de programación dinámica se ha aprovechado para obtener algoritmos de tiempo polinomial en las clases más grandes de gráficos de arco circular [20] y de gráficos de co-comparabilidad (es decir, de los complementos de los gráficos de comparabilidad , que también contienen gráficos de permutación ), [21] ambos tienen el mismo tiempo de ejecución. El último algoritmo se basa en propiedades especiales de la ordenación de vértices de la primera búsqueda en profundidad lexicográfica (LDFS) [22] de los gráficos de co-comparabilidad. Para gráficos de co-comparabilidad, también un algoritmo de tiempo polinomial alternativo con mayor tiempo de ejecuciónse conoce, que se basa en el diagrama de Hasse del conjunto parcialmente ordenado definido por el complemento del gráfico de co-comparabilidad de entrada. [23]
Además, el problema de la ruta más larga se puede resolver en tiempo polinomial en cualquier clase de gráficos con ancho de árbol limitado o ancho de camarilla limitado, como los gráficos de distancia hereditaria . Finalmente, es claramente NP-difícil en todas las clases de gráficos en las que el problema de la trayectoria hamiltoniana es NP-difícil, como en gráficos divididos , gráficos circulares y gráficos planos .
Un modelo simple de un gráfico acíclico dirigido es el modelo de Price , desarrollado por Derek J. de Solla Price para representar redes de citas . Esto es lo suficientemente simple como para permitir la búsqueda de resultados analíticos para algunas propiedades. Por ejemplo, la longitud de la ruta más larga, desde el n-ésimo nodo agregado a la red hasta el primer nodo de la red, se escala como [24] .
Ver también
- Teorema de Gallai-Hasse-Roy-Vitaver , una relación de dualidad entre las trayectorias más largas y el color del gráfico
- El camino del caballero más largo sin cruzar
- Snake-in-the-box , el camino inducido más largo en un gráfico de hipercubo
- El modelo de Price , un modelo de red de citas simple donde las longitudes de ruta más largas se pueden encontrar analíticamente
Referencias
- ^ Schrijver, Alexander (2003), Optimización combinatoria: poliedros y eficiencia, Volumen 1 , Algoritmos y combinatoria, 24 , Springer, p. 114, ISBN 9783540443896.
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos (2ª ed.), MIT Press, p. 978, ISBN 9780262032933.
- ^ Lawler, Eugene L. (2001), Optimización combinatoria: redes y matroides , Publicaciones de Courier Dover, p. 64, ISBN 9780486414539.
- ^ a b c Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algoritmos (4ª ed.), Addison-Wesley Professional, págs. 661–666, ISBN 9780321573513.
- ^ 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.
- ^ a b Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev (2004), "Aproximación de trayectorias y ciclos dirigidos más largos", Proc. En t. Coll. Autómatas, lenguajes y programación (ICALP 2004) , Lecture Notes in Computer Science , 3142 , Berlín: Springer-Verlag, págs. 222-233, MR 2160935.
- ^ Gabow, Harold N .; Nie, Shuxin (2008), "Encontrar caminos, ciclos y circuitos largos", Simposio internacional sobre algoritmos y computación , Lecture Notes in Computer Science, 5369 , Berlín: Springer, págs. 752–763, doi : 10.1007 / 978-3- 540-92182-0_66 , ISBN 978-3-540-92181-3, MR 2539968. Para trabajos anteriores con límites de aproximación aún más débiles, consulte Gabow, Harold N. (2007), "Encontrar caminos y ciclos de longitud superpolilogarítmica" (PDF) , SIAM Journal on Computing , 36 (6): 1648–1671, doi : 10.1137 / S0097539704445366 , MR 2299418 y Björklund, Andreas; Husfeldt, Thore (2003), "Finding a path of superlogarithmic length" , SIAM Journal on Computing , 32 (6): 1395–1402, doi : 10.1137 / S0097539702416761 , MR 2034242.
- ^ 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.
- ^ a b Alon, Noga ; Yuster, Rafael; Zwick, Uri (1995), "Codificación de colores", Journal of the ACM , 42 (4): 844–856, doi : 10.1145 / 210332.210337 , MR 1411787 , S2CID 208936467.
- ^ Bodlaender, Hans L. (1993), "En pruebas menores de tiempo lineal con búsqueda en profundidad primero", 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, consulte Monien, B. (1985), "Cómo encontrar caminos largos de manera eficiente", Análisis y diseño de algoritmos para problemas combinatorios (Udine, 1982) , North-Holland Math. Stud., 109 , Amsterdam: North-Holland, págs. 239-254, doi : 10.1016 / S0304-0208 (08) 73110-4 , ISBN 9780444876997, MR 0808004.
- ^ Chen, Jianer; Lu, Songjian; Sze, Sing-Hoi; Zhang, Fenghui (2007), "Algoritmos mejorados para problemas de ruta, coincidencia y empaque", Proc. 18o Simposio ACM-SIAM sobre algoritmos discretos (SODA '07) (PDF) , págs. 298–307.
- ^ Koutis, Ioannis (2008), "Algoritmos algebraicos más rápidos para problemas de ruta y empaquetamiento", Coloquio internacional sobre autómatas, lenguajes y programación (PDF) , Lecture Notes in Computer Science, 5125 , Berlín: Springer, págs. 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.
- ^ Williams, Ryan (2009), "Encontrar caminos de longitud k en el tiempo O * (2 k )", Information Processing Letters , 109 (6): 315–318, arXiv : 0807.3026 , doi : 10.1016 / j.ipl.2008.11. 004 , MR 2.493.730 , S2CID 10295448.
- ^ Fomin, Fedor V .; Golovach, Petr A .; Lokshtanov, Daniel; Saurabh, Saket (2009), "Ancho de camarilla: sobre el precio de la generalidad", Proc. 20 de ACM-SIAM Simposio sobre discreto Algoritmos (SODA '09) (PDF) , pp. 825-834, Archivado desde el original (PDF) en 10/18/2012 , recuperada 2012-12-01.
- ^ Bulterman, RW; van der Sommen, FW; Zwaan, G .; Verhoeff, T .; van Gasteren, AJM (2002), "Sobre el cálculo de una ruta más larga en un árbol", Information Processing Letters , 81 (2): 93–96, doi : 10.1016 / S0020-0190 (01) 00198-3.
- ^ Uehara, Ryuhei; Uno, Yushi (2004), "Algoritmos eficientes para el problema de la ruta más larga", Isaac 2004 , Lecture Notes in Computer Science, 3341 : 871–883, doi : 10.1007 / 978-3-540-30551-4_74 , ISBN 978-3-540-24131-7.
- ^ Uehara, Ryuhei; Valiente, Gabriel (2007), "Estructura lineal de grafos de permutación bipartita 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.
- ^ Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei (2008), "Problemas de ruta más larga en grafos ptolemaicos", Transacciones IEICE , 91-D (2): 170-177, doi : 10.1093 / ietisy / e91-d.2.170.
- ^ Ioannidou, Kyriaki; Mertzios, George B .; Nikolopoulos, Stavros D. (2011), "El problema de la ruta más larga tiene una solución polinomial en los gráficos de intervalo", Algorithmica , 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , doi : 10.1007 / s00453-010-9411 -3 , S2CID 7577817.
- ^ Mertzios, George B .; Bezakova, Ivona (2014), "Calcular y contar las rutas más largas en gráficas de arco circular en tiempo polinomial", Matemáticas aplicadas discretas , 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi : 10.1016 / j.dam .2012.08.024.
- ^ Mertzios, George B .; Corneil, Derek G. (2012), "Un algoritmo polinomial simple para el problema de ruta más larga en gráficos de cocomparabilidad", SIAM Journal on Discrete Mathematics , 26 (3): 940–963, arXiv : 1004.4560 , doi : 10.1137 / 100793529 , S2CID 4645245.
- ^ Corneil, Derek G .; Krueger, Richard (2008), "Una vista unificada de la búsqueda de gráficos", SIAM Journal on Discrete Mathematics , 22 (4): 1259-1276, doi : 10.1137 / 050623498.
- ^ Ioannidou, Kyriaki; Nikolopoulos, Stavros D. (2011), "El problema de la ruta más larga es polinomio en gráficos de cocomparabilidad" (PDF) , Algorithmica , 65 : 177-205, CiteSeerX 10.1.1.415.9996 , doi : 10.1007 / s00453-011-9583-5 , S2CID 7271040.
- ^ Evans, TS; Calmon, L .; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model", Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038 / s41598-020-67421-8 , PMC 7324613 , PMID 32601403
enlaces externos
- " Find the Longest Path ", canción de Dan Barrett