6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ do you want the tree to be arborescence? or undirected tree? $\endgroup$ – RubyDubee Jan 4 '11 at 22:42
  • $\begingroup$ arborescence rooted at $s$ $\endgroup$ – Imran Rauf Jan 4 '11 at 22:49
  • $\begingroup$ Please edit your question so that people do not have to read the comments to understand what is being asked. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 2:23
  • $\begingroup$ Aren't arborescence and directed tree both rooted at $s$ the same thing in DAG.? $\endgroup$ – Imran Rauf Jan 5 '11 at 7:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 9:05
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 5 '11 at 1:26
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 1:55
  • $\begingroup$ Many thanks Tsuyoshi for the elegant proof! I had the intution that the problem must be NP-complete, but somehow couldn't prove it. $\endgroup$ – Imran Rauf Jan 5 '11 at 7:46
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.