# 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?

• do you want the tree to be arborescence? or undirected tree? – RubyDubee Jan 4 '11 at 22:42
• arborescence rooted at $s$ – Imran Rauf Jan 4 '11 at 22:49
• Please edit your question so that people do not have to read the comments to understand what is being asked. – Tsuyoshi Ito Jan 5 '11 at 2:23
• Aren't arborescence and directed tree both rooted at $s$ the same thing in DAG.? – Imran Rauf Jan 5 '11 at 7:51
• @Imran: The comment by Webbisshh suggests that the use of the word “subtree” in the question (whether it means a directed tree or an undirected tree) can be ambiguous, at least to some people. – Tsuyoshi Ito Jan 5 '11 at 9:05

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 aiSj.
• 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 nmk.

• Clever! Do you mind if I put it into the original proof list? Or do you think it is at the level of an observation? – Hsien-Chih Chang 張顯之 Jan 5 '11 at 1:26
• @Hsien-Chih: Thanks. Not sure this time. :) But it may have appeared in the literature, so probably it is better to wait for a while anyway. – Tsuyoshi Ito Jan 5 '11 at 1:55
• Many thanks Tsuyoshi for the elegant proof! I had the intution that the problem must be NP-complete, but somehow couldn't prove it. – Imran Rauf Jan 5 '11 at 7:46

What about picking, for any vertex different from the source, an incoming arc with maximum weight ? Each vertex except the source is of indegree one, and you needn't worry about circuits as you are in a DAG.

• This works when all edge weights are positive. With negative weight, we may need to discard some of the nodes. – Imran Rauf Jan 4 '11 at 22:07
• Oops ! Got it :-) – Nathann Cohen Jan 5 '11 at 12:50