Finding maximum weight arborescence in an edge-weighted DAG Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$.

When all edge weights are positive then the required arborescence is also spanning and so we can use the directed minimum spanning tree algorithm (http://www.ce.rit.edu/~sjyeec/dmst.html)

What if negative weights are allowed?
The problem is NP-complete by a reduction from the set cover problem.

Set cover
Instance: A finite set U, a family C of subsets of U and k∈ℕ.
Question: Is there a cover D of U in C with at most k sets, that is, a subset D of C with |D|≤k such that the union of D is equal to U?

Given an instance (U, C, k) of the set cover problem, let U={a1, …, an} and C={S1, …, Sm} (n=|U|, m=|C|) and construct a DAG G with four layers of vertices:


The first layer consists of a single source s.
The second layer consists of m vertices x1, …, xm, each of which has an incoming edge from s with weight −1.
The third layer consists of n vertices y1, …, yn.  The vertex yi has an incoming edge from the vertex xj with weight 0 for each pair (i, j) such that ai∈Sj.
The fourth layer consists of n vertices z1, …, zn.  Each vertex zi has an incoming edge from the corresponding vertex yi with weight m.


Then it is easy to see that there is a cover of U in C with at most k sets if and only if the DAG G has an arborescence rooted at s with total weight at least nm−k.