Simple reduction (NP completeness)
Posted
by Allen
on Stack Overflow
See other posts from Stack Overflow
or by Allen
Published on 2009-11-20T02:16:00Z
Indexed on
2010/04/11
4:03 UTC
Read the original article
Hit count: 355
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
© Stack Overflow or respective owner