Timeline for Paths of given "cost" in a graph?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 28, 2012 at 13:37 | vote | accept | Kris | ||
| Jun 28, 2012 at 13:37 | vote | accept | Kris | ||
| Jun 28, 2012 at 13:37 | |||||
| Jun 28, 2012 at 13:37 | vote | accept | Kris | ||
| Jun 28, 2012 at 13:37 | |||||
| Jun 26, 2012 at 22:55 | comment | added | Will Sawin | To prove NP-completeness, you have to prove the subset-sum problem reduces to it. In my second paragraph, I describe a special case of the problem you posted that is the same as the subset-sum problem. Therefore, your problem is NP-complete, because it's special case, the subset-sum problem, is NP-hard. The problem of "does there exist a path of a given cost" is clearly NP, since it takes polynomial time to compute the cost of a path. Thus it is NP-complete. The problem of "find all paths of a given cost" is not NP because it is not a yes-no decision problem. | |
| Jun 26, 2012 at 20:48 | comment | added | Kris | I have a question. Every path does correspond to a subset in the subset-sum problem, however not every subset necessarily correspond to a path (a path needs to be set of continuous edges). In other words, even though the problem I posted is a special case of subset-sum problem, can it be reduced to subset-sum problem in order to prove NP-completeness. Thanks! | |
| Jun 26, 2012 at 18:37 | vote | accept | Kris | ||
| Jun 28, 2012 at 13:37 | |||||
| Jun 25, 2012 at 18:39 | history | answered | Will Sawin | CC BY-SA 3.0 |