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
Did you try Google? 3rd hit is:
http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_416/_article
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.