3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Aug 11, 2015 at 12:13
  • $\begingroup$ @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. $\endgroup$
    – Coffee_Table
    Commented Aug 11, 2015 at 19:15
  • $\begingroup$ @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 en.wikipedia.org/wiki/…). 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. $\endgroup$
    – Coffee_Table
    Commented Aug 11, 2015 at 20:30
  • $\begingroup$ @Saeed Are you sure? As far as I understand, the longest path in a weighted DAG can be solved in polynomial time (see also cs.cmu.edu/~eugene/teach/algs00b/works/s9.pdf, Problem 2). $\endgroup$
    – George
    Commented Aug 12, 2015 at 15:17
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Commented Aug 12, 2015 at 16:14

1 Answer 1

Reset to default
7
$\begingroup$

This is NP-hard by reduction from subset sum. ​ ​ ​ There is a vertex for each element of the
set and one more vertex. ​ ​ ​ The extra vertex has an outgoing edge to each other vertex
but no incoming edges, and otherwise there is an edge from x to y if and only if ​ x < y .
The weight of each edge is equal to that edge's terminal vertex.

However, one can topologically sort the vertices and then use dynamic programming
in a way that's similar to the dynamic programming algorithm for subset sum.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What about the constraint W? It should be W = 0, right? $\endgroup$
    – George
    Commented Aug 12, 2015 at 15:18
  • 1
    $\begingroup$ W is the subset sum instance's upper bound. $\;$ $\endgroup$
    – user6973
    Commented Aug 12, 2015 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.