<p>Another way to prove that it is NP-complete consist of noticing that if each label is 1 and $a = \#V$ where $V$ is the set of vertices, we obtain the hamiltonian path problem. It shows too that even if you give an upper bound C, it remains NP-complete.</p>

<p>EDIT: 
My answer is wrong because in DAG, hamiltonian path problem has a polynomial algorithm.</p>

CC BY-SA 2.5
2011-03-11T15:46:39.253Z
The directed Hamiltonian path problem for DAGs is polynomial-time, not NP-complete.
David Eppstein
CC BY-SA 2.5
2011-03-11T23:14:05.047Z
@David Oups, I hadn't read enough carefully the question. Should I delete my answer to prevent people from being misled if they don't read comments ?
Ludovic Patey
CC BY-SA 2.5
2011-03-12T16:44:56.557Z
Currently we have no policy about deleting wrong answers, so you may do anything you want. Edit the answer, as you did, is another solution.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-11T15:20:22.340Z
2011-03-12T08:34:42.010Z
2011-03-12T08:34:42.010Z
Ludovic Patey
<p>Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.</p>

<p>If you assume that $\max w_i&lt;C$ then there's a dynamic programming algorithm with time $O(mnC)$: just process the nodes in a topological ordering, and for each node calculate the set of path lengths by which it can be reached from $s$.</p>

CC BY-SA 2.5
2011-03-11T08:25:27.250Z
Thank you. I suppose something close to $O(mnC)$ can be achieved by replacing $w_i$ by a chain of $w_i$ unlabelled edges and then search for path of *length* $a$?
jerr18
CC BY-SA 2.5
2011-03-11T08:40:36.090Z
Each set is a bitmask of nC bits and you have to propagate these bitmasks across m edges, hence the O(mnC) time bound.
David Eppstein
CC BY-SA 2.5
2011-03-11T09:12:08.473Z
Since you are looking for a path with cost exactly $a$, a bitmask of $a$ bits suffices. Hence $O(nma)$ time holds also without a $\max w_i<C$ bound.
Gianluca Della Vedova
CC BY-SA 2.5
2011-03-11T09:34:28.627Z
@Gianluca the OQ was with non-negative lables so a>=C. Do you mean you can get $O(nma)$ with negative labels?
jerr18
CC BY-SA 2.5
2011-03-11T09:44:22.480Z
... but now I think Gianluca means $O(n+ma)$ since $a$ is a bound on interesting path lenghts (if $w_i\ge0$). Perhaps I should shut up. :)
Radu GRIGore
CC BY-SA 2.5
2011-03-11T10:06:40.767Z
@jerr18 @Radu Yes, it's $O(n+ma)$, and it's on non-negative weights.
Gianluca Della Vedova
CC BY-SA 2.5
2011-03-12T05:42:20.327Z
One additional remark is that one can implement an $O(n+ma)$ algorithm using dynamic programming even if the graph is not a DAG.
arnab
CC BY-SA 2.5
2011-03-12T15:20:39.760Z
@David assuming a bound $C$ would the algorithm stay polynomial when optimizing a second label? I updated the question with a definition.
jerr18
CC BY-SA 2.5
2011-03-12T15:49:50.103Z
Yes, now instead of just maintaining the set of reachable costs maintain a mapping from each reachable cost to the minimum weight of a path with that cost.
David Eppstein
CC BY-SA 2.5
2011-03-11T08:17:48.670Z
2011-03-11T08:17:48.670Z
David Eppstein
<p>Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.</p>

<p>The problem is:</p>

<blockquote>
  <p>Find a path from $s$ to $t$ with cost $a$.</p>
</blockquote>

<p>I suppose this is NP-hard.</p>

<p>Some questions:</p>

<ol>
<li>Would putting a bound $\max w_i &lt; C$ make the problem easier?</li>
<li>What are the best algorithms for this?</li>
<li>Is the problem NP-complete?</li>
</ol>

<p><strong>Update</strong>
What about this modification of <a href="http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html" rel="nofollow">Number: 63 Shortest Weight-Constrained Path</a></p>

<p>To each edge associate second label weight $r_i \in \mathbb{N}$. The weight of a path is the sum of $r_i$.</p>

<p>Assume (possibly small) bound $C$ of the costs $w_i$ and solve:</p>

<p>$cost = a$ and $weight &lt; K$.</p>

<p>Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?</p>

<graph-theory><co.combinatorics><graph-algorithms>
Path of exact cost in edge labelled DAG?
jerr18
# Path of exact cost in edge labelled DAG?

(Asked by: username_0 on 2011-03-11)

Given edge labelled directed acyclic graph with edge labels $w\_i \in \mathbb{N}$ the cost of a path is the sum of the labels.

The problem is:

> Find a path from $s$ to $t$ with cost $a$.

I suppose this is NP-hard.

Some questions:

1. Would putting a bound $\max w\_i < C$ make the problem easier?
2. What are the best algorithms for this?
3. Is the problem NP-complete?

**Update**
What about this modification of [Number: 63 Shortest Weight-Constrained Path](http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html)

To each edge associate second label weight $r\_i \in \mathbb{N}$. The weight of a path is the sum of $r\_i$.

Assume (possibly small) bound $C$ of the costs $w\_i$ and solve:

$cost = a$ and $weight < K$.

Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?

**Tags:** graph-theory, co.combinatorics, graph-algorithms


---

## 2 answers

### Answer by username_2 on 2011-03-11. Score: 13 | Accepted answer

Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.

If you assume that $\max w\_i

> **Comments:**
> **username_0**: Thank you. I suppose something close to $O(mnC)$ can be achieved by replacing $w_i$ by a chain of $w_i$ unlabelled edges and then search for path of *length* $a$?  
> **username_2**: Each set is a bitmask of nC bits and you have to propagate these bitmasks across m edges, hence the O(mnC) time bound.  
> **username_4**: Since you are looking for a path with cost exactly $a$, a bitmask of $a$ bits suffices. Hence $O(nma)$ time holds also without a $\max w_i<C$ bound.  
> **username_0**: @Gianluca the OQ was with non-negative lables so a>=C. Do you mean you can get $O(nma)$ with negative labels?  
> **username_5**: ... but now I think Gianluca means $O(n+ma)$ since $a$ is a bound on interesting path lenghts (if $w_i\ge0$). Perhaps I should shut up. :)  
> **username_4**: @username_0 @Radu Yes, it's $O(n+ma)$, and it's on non-negative weights.  
> **username_6**: One additional remark is that one can implement an $O(n+ma)$ algorithm using dynamic programming even if the graph is not a DAG.  
> **username_0**: @David assuming a bound $C$ would the algorithm stay polynomial when optimizing a second label? I updated the question with a definition.  
> **username_2**: Yes, now instead of just maintaining the set of reachable costs maintain a mapping from each reachable cost to the minimum weight of a path with that cost.  

---

### Answer by username_1 on 2011-03-11. Score: 0

Another way to prove that it is NP-complete consist of noticing that if each label is 1 and $a = \#V$ where $V$ is the set of vertices, we obtain the hamiltonian path problem. It shows too that even if you give an upper bound C, it remains NP-complete.

EDIT:
My answer is wrong because in DAG, hamiltonian path problem has a polynomial algorithm.

> **Comments:**
> **username_2**: The directed Hamiltonian path problem for DAGs is polynomial-time, not NP-complete.  
> **username_1**: @David Oups, I hadn't read enough carefully the question. Should I delete my answer to prevent people from being misled if they don't read comments ?  
> **username_3**: Currently we have no policy about deleting wrong answers, so you may do anything you want. Edit the answer, as you did, is another solution.  

---

