Simple reduction (NP completeness)

Question

hey guys I'm looking for a means to prove that the bicriteria shortest path problem is np complete. That is, given a graph with lengths and weights, I need to know if a there exists a path in the graph from s to t with total length <= L and weight <= W.

I know that i must take an NP complete problem and reduce it to this one. We have at our disposal the following problems to choose from: 3-SAT, independent set, vertex cover, hamiltonian cycle, and 3-dimensional matching.

Any ideas on which may be viable?

thanks

Answer 1

Did you try Google? 3rd hit is:

http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128%5F416/%5Farticle

The article is pay-per-view, but the Google cache supplies the important bit upfront:

"Unfortunately, the multiobjective case ( including the bicriteria case) is NP-complete(3).

and the reference points to:

(3) M. Garey and D. Johnson : Computers, and Intractability : A Guide to the theory of NP-Completeness, New York: Freeman (1979)

which is the standard reference for questions of this form.

So ... have you looked at Garey and Johnson? I don't have a copy here to check, but it was my go-to when I did comps.