Variation on longest path in a DAG

Question

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?

Answer 1

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

Answer 2

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