<p>The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is maximized, subject to the constraint that the sum of the weights is less than or equal to some upper bound W. Hence the title of this post, that the longest path not be "too long".</p>

<p>I am aware that the general longest-path problem is NP-Hard, and that the standard longest-path problem on DAGs is easily solved in O(|V|+|E|) time using topological sort and edge-relaxation (i.e. DP) (or we can solve this as shortest path by negating edge-weights).</p>

<p>I've frustratingly searched for a while on the web and came up with nothing on this problem; one would think that so simple a variant would at least be mentioned somewhere (if even in the general case, not limited to DAGs; or perhaps phrased as a shortest path problem where the path shouldn't be "too short"). </p>

<p>I thought perhaps simply modifying the edge-relaxation condition to include the upper-bound constraint would do the trick, but I realized this is flawed: a "heavier" path may look attractive at the moment, but may end up violating the constraint (and so we should've stuck with the previous, albeit "lighter" estimate). I've not been able to find some alternative way of modifying the DP method to make this go through.</p>

<p>Efficient solutions are appreciated, or, conversely, a proof that this problem is hard. Relevant sources or references would also be appreciated.</p>

CC BY-SA 3.0
2015-08-11T12:13:52.837Z
If the maximum value of each edge is bounded by a polynomial in $|V|$ and $|E|$ then the problem can be solved in polynomial time by adapting the standard dynamic programming algorithm for longest paths. Since the OP mentions that the longest path on DAGs is easily solved in $O(|V|+|E|)$ maybe he/she is assuming that the weights are small?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-11T19:15:39.557Z
@Saeed do you mean as a reduction from subset-sum where the item-weights correspond to the edge-weights of the DAG? If so, I don't think this works since in an arbitrary DAG, not every combination of weights is expressible as a path, and so finding the longest path may not solve subset-sum optimally. the answer below shows a valid transformation.
Coffee_Table
CC BY-SA 3.0
2015-08-11T20:30:30.060Z
@Saeed I still don't understand. Longest weighted path on a DAG is solvable in time O(|V|+|E|) as I mention in the OP (see https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths). And if w = sum of all edge-weights, then we can just ignore w. the problem only becomes nontrivial (and in fact hard) if w is allowed to be less than the sum of the longest path in the DAG.
Coffee_Table
CC BY-SA 3.0
2015-08-12T15:17:12.400Z
@Saeed Are you sure? As far as I understand, the longest path in a weighted DAG can be solved in polynomial time (see also http://www.cs.cmu.edu/~eugene/teach/algs00b/works/s9.pdf, Problem 2).
George
CC BY-SA 3.0
2015-08-12T16:14:52.920Z
@George, you are right, I totally mixed something totally different with this and I don't know why. Coffee_Table, that was my mistake and if you edit the question I'll undo my downvote.
Saeed
<graph-theory><graph-algorithms><directed-acyclic-graph>
Longest path in a DAG that's not too long
Coffee_Table
# Longest path in a DAG that's not too long

(Asked by: username_0 on 2015-08-11)

The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is maximized, subject to the constraint that the sum of the weights is less than or equal to some upper bound W. Hence the title of this post, that the longest path not be "too long".

I am aware that the general longest-path problem is NP-Hard, and that the standard longest-path problem on DAGs is easily solved in O(|V|+|E|) time using topological sort and edge-relaxation (i.e. DP) (or we can solve this as shortest path by negating edge-weights).

I've frustratingly searched for a while on the web and came up with nothing on this problem; one would think that so simple a variant would at least be mentioned somewhere (if even in the general case, not limited to DAGs; or perhaps phrased as a shortest path problem where the path shouldn't be "too short").

I thought perhaps simply modifying the edge-relaxation condition to include the upper-bound constraint would do the trick, but I realized this is flawed: a "heavier" path may look attractive at the moment, but may end up violating the constraint (and so we should've stuck with the previous, albeit "lighter" estimate). I've not been able to find some alternative way of modifying the DP method to make this go through.

Efficient solutions are appreciated, or, conversely, a proof that this problem is hard. Relevant sources or references would also be appreciated.

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: If the maximum value of each edge is bounded by a polynomial in $|V|$ and $|E|$ then the problem can be solved in polynomial time by adapting the standard dynamic programming algorithm for longest paths. Since the OP mentions that the longest path on DAGs is easily solved in $O(|V|+|E|)$ maybe he/she is assuming that the weights are small?  
> **username_0**: @username_3 do you mean as a reduction from subset-sum where the item-weights correspond to the edge-weights of the DAG? If so, I don't think this works since in an arbitrary DAG, not every combination of weights is expressible as a path, and so finding the longest path may not solve subset-sum optimally. the answer below shows a valid transformation.  
> **username_0**: @username_3 I still don't understand. Longest weighted path on a DAG is solvable in time O(|V|+|E|) as I mention in the OP (see https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths). And if w = sum of all edge-weights, then we can just ignore w. the problem only becomes nontrivial (and in fact hard) if w is allowed to be less than the sum of the longest path in the DAG.  
> **username_2**: @username_3 Are you sure? As far as I understand, the longest path in a weighted DAG can be solved in polynomial time (see also http://www.cs.cmu.edu/~eugene/teach/algs00b/works/s9.pdf, Problem 2).  
> **username_3**: @username_2, you are right, I totally mixed something totally different with this and I don't know why. username_0, that was my mistake and if you edit the question I'll undo my downvote.  

---

## 0 answers

