El problema del camino más largo

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 dice simple si no tiene vértices repetidos. La longitud de un camino se puede medir por el número de aristas o (en el caso de gráficos 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 gráficos sin ciclos de peso negativos, el problema de la ruta más larga es NP-difícil y no se puede resolver en tiempo polinomial para gráficos arbitrarios, a menos que P = NP . Pertenecer a una clase de mayor complejidad también significa que el problema es difícil de aproximar . Sin embargo, el problema se resuelve en tiempo lineal en gráficos acíclicos dirigidos , que tienen aplicaciones importantes en problemas de ruta crítica en problemas de programación.

NP-dificultad

La dureza NP del problema no ponderado de encontrar el camino más largo se puede mostrar reduciendo el problema a encontrar un camino hamiltoniano : un gráfico G tiene un camino hamiltoniano si y solo si el camino más largo tiene una longitud n  - 1 , donde n es el número de vértices del gráfico G. _ Dado que el problema de encontrar un camino hamiltoniano es NP-completo, esta reducción muestra que el problema de encontrar el camino más largo en el caso solucionable también es NP-completo. En este problema de resolución, la entrada es un gráfico G y un número k . El resultado esperado es "sí" si G contiene una ruta con k o más arcos, o no en caso contrario [1] .

Si el problema de encontrar el camino más largo pudiera resolverse en tiempo polinomial, podría usarse para resolver este problema de resolución encontrando el camino más largo y comparando la longitud del camino resultante con el número k . Por tanto, el problema de encontrar el camino más largo es NP-difícil. No es NP-completo porque no es un problema de solución [2] .

En grafos completos ponderados con pesos de borde no negativos, el problema de encontrar el camino más largo ponderado es el mismo problema que el problema del viajante de comercio , ya que el camino más largo siempre incluye todos los vértices de este problema [3] .

Grafos acíclicos y caminos críticos

El camino más largo A entre dos vértices dados s y t en un gráfico ponderado G es el mismo que el camino más corto en el gráfico − G obtenido de G al cambiar todos los pesos a pesos con el signo opuesto. Por tanto, si el camino más corto se puede encontrar en − G , entonces también se puede encontrar el camino más largo en G [4] .

Para la mayoría de los gráficos, esta transformación es inútil, ya que crea ciclos de longitud negativa en − G . Pero si G es un gráfico acíclico dirigido , es imposible crear un ciclo negativo y el camino más largo en G se puede encontrar en tiempo lineal aplicando el algoritmo de camino más corto en − G (también un gráfico acíclico dirigido) que corre en tiempo lineal [4] . Por ejemplo, para cualquier vértice v en un gráfico acíclico dirigido, la longitud del camino más largo que termina en v se puede obtener realizando los siguientes pasos:

  1. Realizamos la clasificación topológica del gráfico acíclico dirigido (OAG) dado.
  2. Para cada vértice v del OAG en una ordenación topológica, calculamos la longitud del camino más largo que termina en el vértice v observando los arcos entrantes de los vecinos y sumando uno a la longitud máxima en los registros de estos vecinos. Si v no tiene arcos entrantes, establezca la longitud de la ruta más larga que termina en v en cero.

Cuando se hace esto, se puede obtener la ruta más larga de todo el gráfico comenzando en el vértice v con el valor registrado más grande y trabajando hacia atrás, eligiendo el arco entrante cuya entrada de vértice inicial tenga el valor más grande.

El método de la ruta crítica para programar un conjunto de actividades utiliza la construcción de un gráfico acíclico dirigido en el que los vértices representan los eventos nodales del proyecto y los arcos representan el trabajo a realizar antes y después del evento nodal. A cada arco se le asigna un peso igual al tiempo estimado para completar el trabajo. En dicho gráfico, la ruta más larga desde el primer evento nodal hasta el último es la ruta crítica, que determina el tiempo total de finalización del proyecto [4] .

El camino más largo de los gráficos acíclicos dirigidos también se puede usar para dibujar gráficos capa por capa : colocamos cada vértice v de un gráfico acíclico dirigido G en un nivel cuyo número corresponde a la longitud del camino más largo que termina en v . Como resultado, obtenemos la disposición de los vértices por niveles, en los que el número de niveles será mínimo [5] .

Aproximación

Bjorklund, Hasfeldt y Kanna escribieron que el problema de encontrar el camino más largo en un gráfico no dirigido no ponderado es "notorio por su dificultad para comprender su dificultad de aproximación" [6] . El algoritmo de aproximación de tiempo de ejecución polinomial más conocido proporciona solo una aproximación muy débil, [7] . No es posible para ninguno aproximar el camino más largo con un factor menor que , a menos que NP pertenezca a problemas de tiempo deterministas cuasi-polinómicos . Sin embargo, existe una gran brecha entre este resultado de aproximabilidad y los algoritmos de aproximación conocidos para este problema [8] .

En el caso de grafos no ponderados pero dirigidos, existen resultados de aproximación fuertes bien conocidos. Para cualquier , el problema no se puede aproximar dentro de , a menos que P = NP y, bajo supuestos teóricos fuertes, el problema no se puede aproximar dentro de [6] . Puede usar la técnica de codificación por colores para encontrar una ruta de longitud logarítmica, si existe, pero esta técnica solo brinda un factor de aproximación [9] .

Complejidad parametrizada

El problema de encontrar el camino más largo es fijo-paramétricamente solucionable si se parametriza por la longitud del camino. Por ejemplo, el problema se puede resolver en un tiempo lineal en el tamaño del gráfico de entrada (pero en un tiempo exponencial en la longitud del camino) con un algoritmo que sigue los siguientes pasos:

  1. Realizamos una búsqueda en profundidad en el gráfico. Sea la profundidad del árbol de búsqueda resultante hasta .
  2. Usamos las rutas desde la raíz hasta las hojas del árbol de búsqueda en profundidad en el orden en que se buscan, a diferencia de la descomposición del gráfico de ruta con ancho de ruta .
  3. Usamos programación dinámica para esta descomposición de caminos para encontrar el camino más largo en el tiempo , donde es el número de vértices del gráfico.

Dado que la ruta de salida tiene una longitud de al menos , el tiempo de ejecución también estará limitado por , donde es la longitud de la ruta más larga [10] . Usando un código de colores, la dependencia de la longitud de la ruta se puede reducir a un solo exponencial [11] [12] [13] . Una técnica de programación dinámica similar muestra que el problema de la ruta más larga también tiene solución paramétrica fija en el ancho del árbol del gráfico.

Para gráficos con ancho de camarilla limitado , el problema de la ruta más larga se puede resolver en tiempo polinomial utilizando un algoritmo de programación dinámica. Sin embargo, el grado del polinomio depende del ancho de la camarilla del gráfico, por lo que estos algoritmos no son decidibles con parámetros fijos. La tarea de encontrar el camino más largo parametrizado por el ancho de la camarilla es difícil para la clase de complejidad parametrizada , lo que significa que apenas hay un algoritmo solucionable paramétrico fijo [14] .

Casos especiales de grafos

El problema de la ruta más larga se puede resolver en tiempo polinomial en los complementos de los gráficos de comparabilidad [15] . También se puede resolver en tiempo polinomial en cualquier clase de gráficos con ancho de árbol acotado o ancho de camarilla acotado, como los gráficos heredados por distancia . Sin embargo, el problema es NP-difícil, incluso si nos restringimos a gráficos divididos , gráficos circulares o gráficos planos [16] .

Véase también

Notas

  1. ↑ Schrijver, 2003 , pág. 114.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 978.
  3. ↑ Lawler, 2001 , pág. 64.
  4. ↑ 1 2 3 Sedgewick, Wayne, 2011 , pág. 661–666.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 265–302.
  6. ↑ 1 2 Björklund, Husfeldt, Khanna, 2004 , p. 222–233.
  7. ↑ ( Gabow, Nie 2008 ). Para trabajos anteriores, incluso con una aproximación más débil, véanse los artículos de Gabow ( Gabow 2007 ) y Björklund y Hasfeldt ( Björklund, Husfeldt 2003 ).
  8. ↑ Karger, Motwani y Ramkumar, 1997 , pág. 82–98.
  9. ↑ Alon, Yuster, Zwick, 1995 .
  10. ↑ ( Bodlaender 1993 ). Para un algoritmo decidible de parámetro fijo anterior con una dependencia ligeramente mejor de la longitud de la ruta pero peor dependencia de la longitud del gráfico, consulte Monien 1985 .
  11. ↑ Chen, Lu, Sze, Zhang, 2007 , pág. 298-307.
  12. ↑ Koutis, 2008 , pág. 575-586.
  13. ↑ Williams, 2009 , pág. 315-318.
  14. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2009 , pág. 825–834.
  15. ↑ ( Ioannidou y Nikolopoulos 2011 ). Para trabajos anteriores sobre clases más restringidas, ver ( Ioannidou, Mertzios, Nikolopoulos 2011 ) y ( Uehara, Valiente 2007 ).
  16. ↑ Ioannidou, Mertzios, Nikolopoulos, 2011 .

Literatura

Enlaces