reducción simple (NP-completo)

Question

Estoy buscando un medio para demostrar que el problema del camino más corto bicriteria es NP completo. Es decir, dado un gráfico con longitudes y pesos, que necesita saber si una existe un camino en el gráfico de s a T con longitud total <= L y peso <= W.

Sé que debo tener un problema NP completo y reducirla a éste. Tenemos a nuestra disposición los siguientes problemas para elegir:. 3-SAT, conjunto independiente, cubierta vértice, ciclo de Hamilton, y la coincidencia de 3 dimensiones

¿Alguna idea sobre la que pueden ser viables?

gracias

Answer 1

¿Usted intentó Google? 3er golpe es:

http: //www.jstage.jst .go.jp / article / ieejeiss / 128/3 / 128_416 / _article

El artículo es pago por visión, pero el caché de Google suministra la parte importante por adelantado:

"Desafortunadamente, el caso multiobjetivo (incluyendo el caso bicriteria) es NP-completo (3).

y los puntos de referencia a:

(3) M. Garey y D. Johnson: Informática y Intratabilidad: Una guía para la teoría de NP-completitud, Nueva York: Freeman (1979)

que es el estándar de referencia para cuestiones de esta forma.

Así que ... ¿Has mirado en Garey y Johnson? No tengo una copia aquí para ver, pero era mi go-to cuando lo hice comps.