Get maximum value in directed graph

Question

I have a directed graph where each vertex $k$ is associated with some value $v_k$, and I want to maximize the sum of all the $v_k$ I can get by traversing this graph starting from some given vertex. The graph may be cyclic, but even if I traverse vertex $k$ more than once, I only get the value $v_k$ once.

This seems like a simple enough problem doable by perhaps modifying DFS in some way, but I'm not quite getting the idea on how to solve it.

Answer 1

If negative values are allowed, then this problem is NP-complete, which we can prove by a reduction from the directed Hamiltonian path problem.

Given an $n$-vertex directed graph $G$, do the following:

1. Give each vertex value $2$.
2. Replace each edge $v \to w$ of $G$ by a path $v \to x_{vw} \to w$, where $x_{vw}$ is a new vertex given value $-1$.

No value higher than $n+1$ can be achieved, and a value of $n+1$ is only possible by following a Hamiltonian path in $G$ (picking up all $n$ of the positive-value vertices, and only $n-1$ of the negative-value vertices). So an algorithm that could tell you the maximum value achievable would, in particular, be able to determine whether $G$ contains a Hamiltonian path.

(In your problem, you also specify the starting vertex. This doesn't make a huge difference, since this is easy to reduce to a case where the starting vertex is not specified: just add a source vertex of value $0$ with an edge to all other vertices.)

---

If all vertices have nonnegative values, so that picking up more vertices is always better, then we can solve this problem efficiently.

First, combine each strongly connected component in the graph into a single vertex whose value is the total value of that strongly connected component. (This is called the condensation of the original graph, and can be computed in linear time.) Working with this graph is equivalent to working with the original graph, since once you've visited one vertex in the strongly connected component, you might as well visit them all.

Once we've done this, the graph becomes acyclic. Find a topological ordering of the graph, and consider its vertices in reverse order. For a vertex $v$ with out-neighbors $w_1, w_2, \dots, w_k$, the maximum value we can get starting from $v$ is $f(v) = \text{value}(v) + \max\{0, f(w_1), f(w_2), \dots, f(w_k)\}$. (So if $v$ has no out-neighbors, the maximum value we get is just the value of $v$.)