"Familiares" del problema del camino más corto

Considere un gráfico conectado no dirigido con pesos de borde no negativos y dos vértices distinguidos $s,t$ . A continuación se presentan algunos problemas de ruta que son todos de la siguiente forma: encuentre una ruta $s-t$ , de modo que alguna función de los pesos de borde en la ruta sea mínima. En este sentido, todos son "parientes" del problema del camino más corto; en este último la función es simplemente la suma.

Nota: Estamos buscando caminos simples, es decir, sin vértices repetidos. Como no encontré nombres estándar para estos problemas en la literatura, los nombré yo mismo.

Ruta con espacio de peso mínimo: encuentre una ruta $s-t$ , de modo que la diferencia entre los pesos de borde más grande y más pequeño en la ruta sea mínima.

La ruta más suave: encuentre una ruta $s-t$ , de modo que el tamaño de paso más grande en la ruta sea mínimo, donde un tamaño de paso es el valor absoluto de la diferencia de peso entre dos bordes consecutivos .

Ruta con altitud mínima: definamos la altitud de una ruta mediante la suma de los tamaños de paso a lo largo de la ruta (consulte la definición de tamaño de paso más arriba). Encuentre un camino $s-t$ con altitud mínima.

Ruta con peso primo mínimo: suponiendo que todos los pesos de borde sean enteros positivos, encuentre una ruta $s-t$ , de modo que su peso sea un número primo. Si existe tal camino, encuentre uno con el peso primario más pequeño posible.

Pregunta: ¿qué se sabe sobre estos problemas de ruta? (Y otros que podrían concebirse con un espíritu similar, aplicando una función diferente de los pesos). En general, ¿hay alguna guía de qué funciones de los pesos de borde se pueden minimizar en el tiempo polinómico y cuáles son NP-duras?

Nota: es interesante, por ejemplo, que si bien la suma de los pesos es fácil de minimizar (es el problema clásico de la ruta más corta), pero minimizar el promedio estrechamente relacionado de los pesos en la ruta es NP-duro. (Peso Assign 2 a todos los bordes incidente a $s$ y $t$ , y el peso 1 a todos los otros, entonces un camino peso promedio min será una más larga. $s-t$ ruta).

Aquí hay una respuesta al primer problema:

Ruta con espacio de peso mínimo: encuentre una ruta $s-t$ , de modo que la diferencia entre los pesos de borde más grande y más pequeño en la ruta sea mínima.

Un artículo de 1984 muestra que cada vez que podemos decidir la viabilidad (si existe una solución en el caso no ponderado) para algún problema de optimización combinatoria en el tiempo polinómico, también podemos encontrar en el tiempo polinómico una solución que minimice la diferencia entre el más grande y el más pequeño coeficiente de costo (en el caso ponderado):

S. Martello, WR Pulleyblank, P. Toth, D. de Werra
Problemas de optimización equilibrada
Research Research Letters 3, 1984, páginas 275-278

Esto implica un algoritmo de tiempo polinómico para su pregunta.

$\tilde{O}(|E|^2)$$|E|$$|E|$

$\tilde{O}(|E|)$$|E|^2$$k$$k-1$

$S$$Θ(n/\log n)$$\mathrm{P}^S$incluso para pesos binarios: es suficiente realizar un seguimiento de polinomios de muchos (dependiendo de ) los pesos de trayectoria más bajos en cada punto. Sin embargo, con los pesos principales, es posible que tengamos que diversificar los divisores de las diferencias de peso (en lugar de simplemente hacer un seguimiento de los pesos más bajos), y no está claro si eso es suficiente.$S$

El camino más suave: NP completo. Si permitiéramos las auto-intersecciones, esto sería solucionable en el tiempo , pero para la versión sin auto-intersecciones, aquí hay una reducción de 3-SAT con variables. Tiene vértices , más un vértice para cada cláusula. Para cada variable ( ), agregue una ruta suave (usando vértices adicionales si es necesario) desde a que pase por todas las cláusulas con ocurrencia positiva de , y una ruta similar para cláusulas con$\tilde{O}(|E|)$$n$$s=v_0,v_1,...,t=v_n$$x_i$$i<n$$v_i$$v_{i+1}$$x_i$$¬x_i$. Establezca el primer y último grosor de borde de cada ruta en 1 (u otra constante), pero de lo contrario, elija pesos de manera que ninguna otra ruta sea uniforme. Finalmente, duplique todos los vértices de la cláusula y los bordes adyacentes; De esta manera, cada cláusula se puede visitar como máximo dos veces, lo que es suficiente para 3-SAT.