Cómo demostrar que un problema es NP-duro

Question

Bien, supongamos que tenemos un grafo no dirigido de tamaño finito con aristas con peso = 1. El grafo es disperso. Desde cualquier nodo, hay un camino a cualquier otro nodo.

Ahora, tenemos dos coches en algún lugar del gráfico que van constantemente de un destino a otro. Recorrer una arista lleva exactamente un segundo. Dada cualquier lista de destinos para ambos coches, queremos encontrar las rutas más rápidas para ambos coches. Los destinos de las listas deben ser visitados en orden por sus respectivos coches.

Se trata de dos problemas que, individualmente, podrían resolverse fácilmente con el algoritmo de Dijkstra. Sin embargo, es posible que los coches no colisionen nunca en los nodos. Pueden estar atravesando la misma arista al mismo tiempo, pero nunca pueden estar en el mismo nodo al mismo tiempo.

Se supone que debo encontrar las mejores rutas posibles para los dos coches que resulten en el menor tiempo total utilizando algoritmos codiciosos. Lo que estoy haciendo es usar el algoritmo de Dijkstra para resolver para los dos coches individualmente y luego resolver las colisiones haciendo esperar al coche con el tiempo de llegada más temprano.

Sin embargo, esta no es la solución más óptima. Me han insinuado que este problema es NP-difícil y tengo que demostrarlo o presentar un algoritmo que dé la solución globalmente óptima.

Pero no estoy seguro de que este problema sea realmente NP-duro y me pierdo por completo cuando intento demostrarlo. Sí, hay que reducir el problema en cuestión a un problema conocido de dificultad NP, ¡pero no sé ni por dónde empezar!

¿Puede alguien ayudarme con esto?

Answer 1

A continuación te explicamos cómo puedes hacerlo en tiempo polinómico. Digamos que nos dan el problema sobre el gráfico $G=(V,E)$ . Primero construimos otro gráfico $G' = (V',E')$ . El conjunto de nodos $V'$ será simplemente $V^2\setminus\{(u,u)|u\in V\}$ . La relación de borde $E'$ será tal que $E'((u,v),(w,x))$ si y sólo si $E(u,w)$ y $E(v,x)$ (sin pérdida de generalidad, suponemos que todos los nodos tienen un bucle propio en $E$ para que la espera pueda ser contabilizada en esta relación de borde). Sea $U = \{u_0,u_1,\ldots,u_n\}$ y $W = \{w_0,w_1,\ldots,w_m\}$ sean las listas de destino de los coches, donde $u_0$ y $w_0$ son las posiciones de salida de los coches. Ahora creamos una copia de $G'$ para cada $u_i,w_j$ que denotamos $G_{i,j}$ (y la copia de un nodo $v \in V'$ se denota por $(v,i,j)$ ). Ponemos todos los gráficos $G_{i,j}$ en un solo gráfico $H$ de la siguiente manera. Sea $i,j$ sea arbitraria. A continuación, añadimos las aristas $((u_{i-1},v,i-1,j),(u_{i-1},v,i,j))$ , $((v,w_{j-1},i,j-1),(v,w_{j-1},i,j))$ para todos $v\in V$ y el borde $((u_{i-1},w_{j-1},i-1,j-1),(u_{i-1},w_{j-1},i,j))$ . Damos a cada una de estas nuevas aristas un peso cero, para que recorrerlas no cueste tiempo.

Entonces simplemente ejecutamos el de Djikstra en $H$ con fuente $(u_0,w_0,0,0)$ y el objetivo $(u_n,w_m,n,m)$ . El tiempo de ejecución de esto será $O([(|V|^2 + |E^2|)nm]^3)$ que es claramente polinómico. En realidad se trata de un algoritmo de programación dinámica.