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: 405

Filed under:

np-complete

|

reduction

|

shortest-path

|

homework

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

Related posts about np-complete

What is an NP-complete problem?

as seen on Stack Overflow - Search for 'Stack Overflow'
What is an NP-complete problem? Why is it such an important topic in computer science? >>> More
The subsets-sum problem and the solvability of NP-complete problems

as seen on Stack Overflow - Search for 'Stack Overflow'
I was reading about the subset-sums problem when I came up with what appears to be a general-purpose algorithm for solving it: (defun subset-contains-sum (set sum) (let ((subsets) (new-subset) (new-sum)) (dolist (element set) (dolist (subset-sum subsets) (setf… >>> More
Is the board game "Go" NP complete?

as seen on Stack Overflow - Search for 'Stack Overflow'
There are plenty of Chess AI's around, and evidently some are good enough to beat some of the world's greatest players. I've heard that many attempts have been made to write successful AI's for the board game Go, but so far nothing has been conceived beyond average amateur level. Could it be that… >>> More
Relating NP-Complete problems to real world problems

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a decent grasp of NP Complete problems; that's not the issue. What I don't have is a good sense of where they turn up in "real" programming. Some (like knapsack and traveling salesman) are obvious, but others don't seem obviously connected to "real" problems. I've had the experience several… >>> More
What is an NP-complete problem?

as seen on Stack Overflow - Search for 'Stack Overflow'
I tried reading previous posts about NP- My question is what does the word "COMPLETE" mean? Why is it there? What is its significance? N- Non-deterministic - makes sense' P- Polynomial - makes sense but the "COMPLETE" is still a mystery for me. >>> More

Related posts about reduction

Simple reduction (NP completeness)

as seen on Stack Overflow - Search for 'Stack Overflow'
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… >>> More
Lookup table size reduction

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello: I have an application in which I have to store a couple of millions of integers, I have to store them in a Look up table, obviously I cannot store such amount of data in memory and in my requirements I am very limited I have to store the data in an embebedded system so I am very limited in… >>> More
Modular Reduction of Polynomials in NTRUEncrypt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello everyone. I'm implementing the NTRUEncrypt algorithm, according to an NTRU tutorial, a polynomial f has an inverse g such that f*g=1 mod x, basically the polynomial multiplied by its inverse reduced modulo x gives 1. I get the concept but in an example they provide, a polynomial f = -1 + X… >>> More
Reduction functions for rainbow tables

as seen on Stack Overflow - Search for 'Stack Overflow'
Since chains of rainbow tables are very long, are there many different reduction functions used to reduce each hash, or are there only a handful, while using indexes to prevent merging? or something else? >>> More
Voices disappear when using headphones.

as seen on Super User - Search for 'Super User'
How do I declare a variable in C? P.S. I have a pair of SteelSeries Siberia headphones. I've noticed that when watching some films the voices are completely silent, yet when I unplug the headset and listen through my speakers they are there and sound normal. I have no other software that could be… >>> More