Redução simples (integridade do NP)

Question

Estou procurando um meio de provar que o problema mais curto do caminho da bicicleta está completo. Ou seja, dado um gráfico com comprimentos e pesos, preciso saber se existe um caminho no gráfico de s a t com comprimento total <= l e peso <= w.

Sei que devo tomar um problema completo do NP e reduzi -lo a este. Temos à nossa disposição os seguintes problemas para escolher: 3-SAT, Conjunto Independente, Capa de Vertex, Ciclo Hamiltoniano e correspondência tridimensional.

Alguma idéia sobre qual pode ser viável?

obrigado

Answer 1

Você tentou o Google? O 3º sucesso é:

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

O artigo é pay-per-view, mas o Google Cache fornece o importante bit inicial:

"Infelizmente, o caso multiobjetivo (incluindo o caso Bicriteria) é NP-complete (3).

e a referência aponta para:

(3) M. Garey e D. Johnson: Computers e Intratabatility: Um Guia para a Teoria da Completude NP, Nova York: Freeman (1979)

Qual é a referência padrão para questões deste formulário.

Então ... você já olhou para Garey e Johnson? Não tenho uma cópia aqui para verificar, mas foi o meu objetivo quando fiz comps.