7
$\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?

Improve this question
$\endgroup$
6
  • $\begingroup$ do you want the tree to be arborescence? or undirected tree? $\endgroup$
    – RubyDubee
    Commented Jan 4, 2011 at 22:42
  • $\begingroup$ arborescence rooted at $s$ $\endgroup$
    – Imran Rauf
    Commented Jan 4, 2011 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
    Commented Jan 5, 2011 at 2:23
  • $\begingroup$ Aren't arborescence and directed tree both rooted at $s$ the same thing in DAG.? $\endgroup$
    – Imran Rauf
    Commented Jan 5, 2011 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
    Commented Jan 5, 2011 at 9:05

2 Answers 2

Reset to default
10
$\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 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.

Improve this answer
$\endgroup$
3
  • $\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 張顯之
    Commented Jan 5, 2011 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
    Commented Jan 5, 2011 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
    Commented Jan 5, 2011 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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