1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Kris
    Commented Jun 26, 2012 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Jun 26, 2012 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .