Prize Collecting

We know that finding a longest path in general is an NP-hard problem. But, finding the longest path of length $k$ where length is defined as the number of hops (number of edges in the path) is not.

Problem: Given a directed weighted graph (with possible positive and negative cycles), find the maximum weight path containing at most $k$ edges.

This can also be framed as prize-collecting problem: If each edge weight represents a prize and you have $k$ levels of energy left, find the maximum amount of prizes you can collect by walking around the graph (you can repeat edges and gain the prize again). We shall now refer to this as the prize-collecting problem.

(As an aside, to detect positive weight cycles, you can negate the edges and run BF and see if it converges after $V - 1$ iterations. If it does not, the graph contains a positive weight cycle).

Idea 1 : Graph Modelling

Transform the input graph into a DAG. How? Make $k$ copies of each node (duplicate the graph $k$ times) and draw edges to connect nodes between 2 adjacent graphs if there is an a edge between those nodes in the original graph. So, all edges point right and the path length is at most $k$ since an edge takes you from one graph to the next. An example is shown below:

Obviously there cannot be any cycles since an edge only points to a node in the next graph (hence, it forms a DAG).

Observe that our newly transformed graph contains $kV$ nodes and $kE$ edges.

Then the problem becomes equivalent to finding the longest path (in terms of sum of weights) in the DAG. We are certain that the maximum path length is $k$. So, we can run the DAG SSSP with negated edges for each source (to see where we should start from)

Because of the obvious symmetry of the graph (since each graph is a duplicate of the other), we only need to run SSSP from one set of nodes (i.e., all nodes of 1 graph). We don’t need to run it from all the nodes of all the graphs even though we are allowed to have lengths $< k$ because in the end, we will look at all nodes and take the maximum value.

This will take $O(kVE)$ time since we are running DAG_SSSP (which takes $O(kV + KE)$ time on the new graph for each source) $V$ times. (Whenever you transform a graph, do not forget to recompute the number of nodes and edges in the new graph).

We can optimize this by creating a dummy node to act as the super source to run the DAG_SSSP from. We connect this dummy node to all the nodes of the first graph from which we want to find the heaviest paths (maximum prizes) (this is a very very common technique to use when you are running an algorithm multiple times for different sources, just create a dummy node). Below, the blue node is the “super source” dummy node:

If we use a dummy node, we are running DAG_SSSP only once from the dummy node (to find the heaviest path in the graph from all the source vertices) which takes $O(kV + kE + E)$ because now you have added $E$ edges to connect the dummy node, and $O(kV)$ time to look at each node in the end to find the maximum prize we can collect. We need to look at all the $kV$ nodes and not just the last level of nodes because we are allowed to travel less than $k$ hops as per the problem. So, the total running time becomes $O(kE)$ (assuming the graph is connected and $E > V$)

Idea 2: DP

If you know the optimal solution for $k - 1$, then it is easy to compute the optimal solution for $k$.

Define $P[v,k]$ to be the maximum prize you can collect starting at $v$ and travelling exactly $k$ steps (notice how we modified our subproblem by ensuring exactly $k$ steps rather than at most, this makes it easier to reason about later - if you had kept it “at most”, you wouldn’t know how many steps you had actually taken and so, you wouldn’t be able to use that to solve larger subproblems and fill the memo table correctly)

Trivially, our base case is $P[v,0] = 0$ for all nodes $v$. That is, if you cannot travel anymore, you cannot win anymore prizes.

The crucial recurrence relation is:

$$P[v,k] = \max\{P[w_1, k-1] + w(v,w_1),P[w_2, k-1] + w(v,w_2), \dots, P[w_n, k-1] + w(v,w_n)\}$$

where $v.nbrList() = \{w_1,w_2, \dots, w_n\}$ and $w(u,v)$ is the cost of an edge from $u$ to $v$.

In other words, if you know the maximum prize you can win if you have $k-1$ steps left from all the neighbours, just calculate the maximum of all the neighbours, while adding the prize won by travelling to each neighbour.

Pseudocode

For every node, you know that the maximum you can earn in 0 steps is 0.

Then for each node, you check how much you can travel if you have 1 step: so look at all its neighbours and pick the maximum weight edge.

Then for each node (say, $v$), you check how much you can travel in 2 steps: look at all the neighbours, and find the maximum neighbour $w_i$ where $P[w_i,1] + w(v,w_i)$ is maximum among all neighbours of $u$. This means starting from $u$ if you have to travel exactly 2 steps, you should go from $u$ to $w_i$ and then from $w_i$ to some other node (depending on the neighbours of $w_i$)

In other words, for each node, calculate how much you would travel in exactly $k$ steps if you went to all your neighbours (essentially, just brute force). But you have already computed how much you can travel from your neighbours in $k-1$ steps so you don’t need to recompute - this is exactly why we fill up the memo table from bottom to top, in increasing order of $k$ for all the nodes. This ensures that we have all the information we need to make the right decision. We look at all possible solution and pick the best one at every step - so, this is a greedy algorithm implemented using DP to avoid the unnecessary recomputation.

Notice that we find the maximum in the entire memo table and not just the last row because the number of edges in the longest path needs to be at most $k$ and not necessarily equal to $k$.

Realize that the main part of this problem was to spot the subproblems and identify the correct recurrence relation - once you do that, the problem is essentially solved.

Time Complexity Analysis

There are $kV$ subproblems: each node has to store $k$ possible values regarding the prizes you can win starting from that node if you travel exactly $k$ steps. In the worst case, each node is connected to all other nodes and we need to look at all other nodes, for every node, $k$ times, giving us a $O(kV^2)$ complexity. But, on closer inspection, this is a pessimistic bound that is only true for very dense graphs. In general, the bound is pretty loose.

A more detailed analysis is as follows:

Each edge is looked at $k$ times, once each time to determine the value of the node using the neighbour’s value. In terms of a table view, think of a 2-D table. There are $k$ rows and $V$ columns. Then, each row is constructed based on the previous row (i.e., $k^{th}$ row requires $(k-1)^{th}$ row answers). Moreover, while filling any row, we look at exactly $E$ entries of the table (in total for the entire row) since we precisely look at each of the neighbours of a node, which adds up to $E$ when we consider all the nodes. So, it takes us about $O(kE)$ to fill the table. Then, to find the maximum value in the table, it takes us $O(kV)$ (size of the table) time. Overall, the time complexity becomes $O(kE)$.