Problema del camino más largo

Problema de encontrar el camino simple más largo para un gráfico determinado

En teoría de grafos e informática teórica , el problema del camino más largo es el problema de encontrar un camino simple de longitud máxima en un gráfico dado . Un camino se llama simple si no tiene vértices repetidos ; La longitud de un camino puede medirse por su número de aristas o (en gráficos ponderados ) por la suma de los pesos de sus aristas. En contraste con el problema del camino más corto , que se puede resolver en tiempo polinómico en gráficos 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 algunos datos dados. longitud, es NP-completo . Esto significa que el problema de decisión no se puede resolver en tiempo polinomial para gráficas arbitrarias a menos que P = NP . También se conocen resultados de dureza más fuertes, lo que demuestra 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 sólo 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 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 gráfico G y un número k ; el resultado deseado es sí si G contiene una ruta de k o más aristas, y no en caso contrario. ^[1]

Si el problema del camino más largo pudiera resolverse en tiempo polinómico, podría usarse para resolver este problema de decisión, encontrando el camino más largo y luego 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 una ruta simple en un gráfico dado con al menos k aristas" es NP-completa. ^[2]

En gráficos completos ponderados con pesos de borde 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]

Gráficos acíclicos

Un camino más largo entre dos vértices s y t dados en un gráfico ponderado G es lo mismo que un camino más corto en un gráfico - G derivado 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 se pueden encontrar en G. ^[4]

Para la mayoría de los gráficos, esta transformación no es útil porque crea ciclos de longitud negativa en − G. Pero si G es un gráfico 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 las rutas más cortas en − G , que también es un gráfico acíclico dirigido (DAG). gráfico acíclico. ^[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 determinado, la longitud del camino más largo que termina en v se puede obtener mediante los siguientes pasos:

1. Encuentre 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 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 en Por aquí.

Esto equivale 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 se pondera según una estimación de la cantidad de tiempo que tardará en completarse la actividad correspondiente. En dicho gráfico, el camino más largo desde el primer hito hasta el último es el camino crítico, 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 número posible de capas. ^[5]

Aproximación

Björklund, Husfeldt y Khanna (2004) escriben que el problema del camino más largo en gráficos no ponderados y 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 logra sólo 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 el camino más largo dentro de un factor de 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] ${\displaystyle 2^{(\log n)^{1-\epsilon }}}$

En el caso de gráficos no ponderados pero dirigidos, se conocen fuertes resultados de inaproximabilidad. Para cada uno, el problema no se puede aproximar dentro de un factor de a menos que P = NP, y con supuestos de teoría 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 relación de aproximación de sólo . ^[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 es manejable 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 del camino), mediante un algoritmo que realiza los siguientes pasos:

1. Realice una búsqueda en profundidad del gráfico. 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 que fueron atravesadas 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 rutas para encontrar la ruta más larga en el tiempo , donde está 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 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 está parametrizado por el ancho del árbol del gráfico. ${\displaystyle d}$ ${\displaystyle O(\ell !2^{\ell }n)}$ ${\displaystyle \ell }$

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 camarilla, 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 en 2002 se publicó una prueba formal de este algoritmo. ^[15] Además, se puede calcular un camino más largo 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 , se conoce un 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 mayores 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 . Este último algoritmo se basa en propiedades especiales del ordenamiento de vértices de la primera búsqueda lexicográfica en profundidad (LDFS) ^[22] de gráficos de co-comparabilidad. Para los gráficos de co-comparabilidad también se conoce un algoritmo alternativo de tiempo polinomial con mayor tiempo de ejecución , 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] ${\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 polinómico en cualquier clase de gráficos con ancho de árbol acotado o ancho de camarilla acotado, como los gráficos hereditarios de distancia . Finalmente, es claramente NP-duro en todas las clases de gráficos en las que el problema de la ruta hamiltoniana es NP-duro, como en gráficos divididos , gráficos circulares y gráficos planos .

Un modelo simple de 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 encontrar resultados analíticos para algunas propiedades. Por ejemplo, la longitud de la ruta más larga, desde el enésimo nodo agregado a la red hasta el primer nodo de la red, escala como ^[24] . ${\displaystyle \ln(n)}$

Ver también

• Teorema de Gallai-Hasse-Roy-Vitaver , una relación de dualidad entre caminos más largos y coloración de gráficos
• El camino de caballero más largo sin cruzar
• Snake-in-the-box , el camino inducido más largo en un gráfico de hipercubo
• Modelo de Price , un modelo de red de citas simple donde las longitudes de camino 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. 978, ISBN 9780262032933.
3. Lawler, Eugene L. (2001), Optimización combinatoria: redes y matroides, Publicaciones Courier Dover, p. 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, Pedro ; Tamasia, 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 caminos dirigidos más largos", Proc. En t. Col. Autómatas, lenguajes y programación (ICALP 2004) , Apuntes de conferencias en informática , vol. 3142, Berlín: Springer-Verlag, págs. 222–233, SEÑOR  2160935.
7. Gabow, Harold N .; Nie, Shuxin (2008), "Encontrar caminos, ciclos y circuitos largos", 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, señor  2539968. Para trabajos anteriores con límites de aproximación aún más débiles, consulte Gabow, Harold N. (2007), "Finding paths and Cycles of superpolylogarithmic length" (PDF) , SIAM Journal on Computing , 36 (6): 1648–1671, doi :10.1137/ S0097539704445366, señor  2299418y Bjorklund, 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 del camino más largo en un gráfico", Algorithmica , 18 (1): 82–98, doi :10.1007/BF02523689, MR  1432030, S2CID  3241830.
9. 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.
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 conocer un algoritmo FPT anterior con una dependencia ligeramente mejor de la longitud de la ruta, pero una peor dependencia del tamaño del gráfico, consulte Monien, B. (1985), "How to find long paths eficientemente", Análisis y diseño de algoritmos para problemas combinatorios. (Udine, 1982), Matemáticas de Holanda Septentrional. Stud., vol. 109, Ámsterdam: Holanda Septentrional, págs. 239–254, doi :10.1016/S0304-0208(08)73110-4, ISBN 9780444876997, SEÑOR  0808004.
11. Chen, Jianer; Lu, Songjian; Sze, Sing-Hoi; Zhang, Fenghui (2007), "Algoritmos mejorados para problemas de ruta, coincidencia y empaquetado", 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 ruta y empaquetado", Coloquio internacional sobre autómatas, lenguajes y programación (PDF) , Lecture Notes in Computer Science, vol. 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 9 de agosto de 2017 , consultado el 9 de agosto de 2013.
13. Williams, Ryan (2009), "Encontrar caminos de longitud k en O * (2 ^k ) tiempo", Cartas de procesamiento de información , 109 (6): 315–318, arXiv : 0807.3026 , doi : 10.1016/j.ipl.2008.11 .004, SEÑOR  2493730, S2CID  10295448.
14. Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2009), "Ancho de camarilla: sobre el precio de la generalidad", Proc. 20.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '09) (PDF) , págs. 825–834, archivado desde el original (PDF) el 18 de octubre de 2012 , consultado el 1 de diciembre de 2012.
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 del camino más largo", en Fleischer, Rudolf; Trippen, Gerhard (eds.), Algoritmos y Computación, 15º Simposio Internacional, ISAAC 2004, Hong Kong, China, 20 al 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 del camino más largo", 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 del camino más largo en gráficos 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 del camino más largo tiene una solución polinómica en gráficos de intervalo", 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), "Calcular y contar caminos más largos en gráficos 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 .
21. Mertzios, George B.; Corneil, Derek G. (2012), "Un algoritmo polinómico simple para el problema del camino más largo en gráficos de 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 vista unificada de la búsqueda de gráficos", Revista SIAM de Matemáticas Discretas , 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; Calmón, 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