Variation on longest path in a DAG

Consider a directed acyclic graph with $n$ nodes and $m$ edges. Each edge is assigned a positive weight. There is a start node $s$ and an end node $e$. We want to find the path from $s$ to $e$ that has the maximum number of nodes such that

1. the total distance is less than some constant $d$, and
2. starting from $s$, each node in the path is closer than the previous one to the node $e$. (As in, when you traverse the path you are getting closer to your destination $e$ in terms of the edge weight of the remaining path.)

Does a polynomial time algorithm already exist for this problem? Is there a formal name for this problem?

• Can you clarify what you mean in (2) by "closer"? It reads as if you mean with respect to distance along the chosen path, but choosing any simple path would give you that property, I think, so it doesn't quite make sense. In any case, isn't this an easy dynamic programming exercise? Mar 15, 2013 at 3:25
• @Neal Young, Closer means that as you go through the path you reduce the distance remaining between you and your destination. Do you know the name of this problem? Mar 15, 2013 at 10:51
• When you say distance remaining, what precisely do you mean? Do you mean the length of the shortest path (from where you are to $e$) (i) in the original graph or (ii) along the chosen path? (I read it as the latter, which doesn't make sense to me, because the distances will be decreasing along any path.) If you mean the former, isn't the problem easy? Just delete all edges $(u,w)$ such that distance$(u,e)<$distance$(w,e)$, then find the longest path (meaning, path with the most edges) in the resulting DAG using the standard dynamic programming algorithm for longest path in a DAG. Mar 17, 2013 at 2:48

You could solve it using a dynamic programming approach:

First lay out vertices in a topological order like $v_1, v_2, ..., v_n$. If start and end vertices are $s=v_a$ and $e=v_b$, you could get rid of all vertices after $v_b$ and before $v_a$. So let's assume $s=v_1$ and $e=v_n$. Next, define $L_{i,j,p}$ to be the shortest path between $v_i$ and $v_j$ which has $p$ nodes. In other words, among paths between $v_i, v_j$ which have $p$ nodes, it's the length of shortest one. Assume $w_{i,j}$ is the weight between $v_i, v_j$, and it is infinity if there is no edge. Now

1. Set $L_{i,i,1}=0$.
2. For $p>1$ we have $L_{i,j,p} = min_k \{L_{i,k,p-1}+w_{k,j} \}$, where $i\le k<j$.

Now the final answer is $max\{k\}$ for all $k$s that we have $L_{1,n,k}<d$. The table (actually half of it need to be filled, because $i<j$) has $n^3$ elements, and for each element $O(n)$ time it takes to be computed. So the time complexity will be $O(n^4)$, but guess tighter bounds could be achieved.

UPDATE: As Neals pointed out in the comments an $O(n^2 m)$ bound is achievable. Also the algorithm can be thought of as a LDP algorithm running on transformed graph $G'$: make $n$ copies of the original graph $G$ and for each edge $e=(v,w)$ in $G$ connect the $i$th copy of $v$ and $(i+1)$th copy of $w$, for $1 \le i < n$.

• With a careful implementation, you get $O(n^2m)$, right? For a given $p$, you can get $L_{i,k,p}$ for all $i$ and $j$ by considering each edge just once. Mar 17, 2013 at 15:50
• p.s. One can think of your algorithm as running the linear-time dynamic programming algorithm for single-source shortest-paths in a DAG, where the DAG is obtained from $G$ by making $n$ copies of each vertex, and, for each edge $(u,w)$ in $G$, adding an edge from the $i$th copy of $u$ to the $i+1$'st copy of $w$ (so every path from the first copy of $s$ to the $i$th copy of any $v$ has $i-1$ edges). Mar 17, 2013 at 16:06
• Very very nice insight. I'm adding your point to the post. Mar 17, 2013 at 16:16

First, for the “getting closer” part, I agree with Neil Young: If you mean “the distance remaining along the solution path,” that follows from the fact that you have positive edge weights. If you mean “the shortest distance from the node to $e$ along any path will decrease” then you can just first compute all distances (normal shortest paths) to $e$ and delete all edges that increase this, as they cannot be part of the solution.

As for the remainder of the solution, you can indeed solve that by dynamic programming, but not just the one with the maxmimum number of nodes—there may be many such paths, and not all of them will necessarily have a weighted length below your given threshold. You can solve it, though, and even with an out-of-the-box shortest path algorithm, by simply modifying the weights (assuming you've deleted any offending edges, as described above, if that's what you meant in your problem description; otherwise, you don't need to do any of that).

The idea is that in order to find a path with a length below a given threshold, you can simply find the shortest one. If it's not below the threshold, no such path could be found anyway. The only remaining wrinkle is how to find the path among those with the maximum number of nodes (i.e., edges, as you have one more node than edges in a path) that has the minimum edge sum (i.e., weighted length).

To do this, you can use the standard trick of having to “digits” in your cost. The idea here is that you have two different costs or objective functions, but one takes precedence, that is, it forms the “most significant digit” in the cost value. By simply multiplying this cost with a high enough value, you get what you want. So basically, you just find the shortest path from $s$ to $e$ where each $(u, v)$ has a cost of $-k + w(u,v)$, where $k$ is some large (enough) constant. (If you have $m$ edges, and the maximum edge cost is $W$, you could for example let $k=m\cdot W$, as this would be larger than the length of any path.)

This basically makes each step in your path add a cost of $-k$, which means that it will always pay to find a path with more edges (and thereby, nodes) regardless of the weighted length (sum of $w(·\,,·)$) of the path. In this way, you're guaranteed to find the one with the most nodes, as you require. However, among the paths with the maximum number of nodes, you will get the same number of $-k$ values, but the sum of the edge weights $w(u,v)$ will vary, and it will always pay to minimize this (and therefore, any shortest-path algorithm will minimize it). In this way, among the paths with the maximum number of nodes, you will find the shortest one (i.e., with the lowest edge sum). If this weighted length is below the threshold $d$, you've solved your problem. If it is not, there is no solution.

This will work not only for DAGs, but (if you use Bellman-Ford, for example, rather than the plain DAG-Shortest-Path) for general directed graphs where no cycles can be reached from $s$. (Any cycle in the graph will yield a negative cycle with the given weighte function, because $k$ is so large.)

• You can't do that. Suppose maximum number of vertices in a path is $V$, and among these paths there is no path with length shorter than $d$. But there is a path with $V-1$ nodes which has a length shorter than $d$ and is the answer. In other words, the number of nodes has not total precedence over the length. Mar 17, 2013 at 13:22
• I think Ameer is right -- you can't give the distance complete precedence in your cost function, because you want to find any path with distance at most $d$ (not a path with minimum distance). And if you give the number of vertices on the path precedence, then you might not find a path with length at most $d$, even if one exists. Mar 17, 2013 at 15:47
• I guess I misinterpreted the question. I thought you wanted the path with a maximum number of vertices, and then you had some additional constraints, if possible. I guess you meant it the other way around—i.e., among the paths that satisfy your constraints you want the one with the most vertices. If so, sure, my solution doesn't apply :) Mar 18, 2013 at 9:11
• Ah,with that interpretation of the problem, I agree with your algorithm. Mar 20, 2013 at 3:30