Simple reduction (NP completeness)
- by Allen
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