Hi,


Consider a graph where each link has a cost assigned to it. I am trying to compute all paths of a given cost in a graph. I am considering both cases - where links/edges CAN repeat and CANNOT repeat. 


Is there any efficient algorithm or is this proven to be NP-complete/hard.


Thanks in advance.



Paths of given "cost" in a graph?
The list of paths itself can be exponentially long. In this case you clearly have no hope of finding the list in polynomial time. Take the graph with two edges from the first to the second vertex, two edges from the second to the third, and so on for $n+1$ vertices. (To make this graph simple, subdivide the edges.) Then there are at least $2^n$ paths of the same cost.


The NP-complete [subset sum problem](http://en.wikipedia.org/wiki/Subset_sum_problem) is also strongly related. The subset-sum problem, which asks whether there is a subset of a certain set of integers that sums to a certain integer, reduces to a special case of this problem. Take the same graph as before, but instead giving the edges the same cost, have one edge cost $0$ and the other cost one of the elements of the set. Then the cost of every path is the sum of a subset, and vice versa. Therefore, finding out whether there exists a path of a certain cost at all is NP-hard.


