<p>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.</p>

CC BY-SA 2.5
2011-01-04T22:07:28.300Z
This works when all edge weights are positive. With negative weight, we may need to discard some of the nodes.
Imran Rauf
CC BY-SA 2.5
2011-01-05T12:50:18.210Z
Oops ! Got it :-)
Nathann Cohen
CC BY-SA 2.5
2011-01-04T21:54:56.670Z
2011-01-04T21:54:56.670Z
Nathann Cohen
<p>The problem is NP-complete by a reduction from the set cover problem.</p>

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

<p>Given an instance (<i>U</i>, <i>C</i>, <i>k</i>) of the set cover problem, let <i>U</i>={<i>a</i><sub>1</sub>, …, <i>a</i><sub><i>n</i></sub>} and <i>C</i>={<i>S</i><sub>1</sub>, …, <i>S</i><sub><i>m</i></sub>} (<i>n</i>=|<i>U</i>|, <i>m</i>=|<i>C</i>|) and construct a DAG <i>G</i> with four layers of vertices:</p>

<ul>
<li>The first layer consists of a single source <i>s</i>.</li>
<li>The second layer consists of <i>m</i> vertices <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>m</i></sub>, each of which has an incoming edge from <i>s</i> with weight −1.</li>
<li>The third layer consists of <i>n</i> vertices <i>y</i><sub>1</sub>, …, <i>y</i><sub><i>n</i></sub>.  The vertex <i>y</i><sub><i>i</i></sub> has an incoming edge from the vertex <i>x</i><sub><i>j</i></sub> with weight 0 for each pair (<i>i</i>, <i>j</i>) such that <i>a</i><sub><i>i</i></sub>∈<i>S</i><sub><i>j</i></sub>.</li>
<li>The fourth layer consists of <i>n</i> vertices <i>z</i><sub>1</sub>, …, <i>z</i><sub><i>n</i></sub>.  Each vertex <i>z</i><sub><i>i</i></sub> has an incoming edge from the corresponding vertex <i>y</i><sub><i>i</i></sub> with weight <i>m</i>.</li>
</ul>

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

CC BY-SA 2.5
2011-01-05T01:26:44.797Z
Clever! Do you mind if I put it into the [original proof list](http://meta.cstheory.stackexchange.com/q/784/1800)? Or do you think it is at the level of an observation?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-05T01:55:18.993Z
@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
CC BY-SA 2.5
2011-01-05T07:46:06.350Z
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
CC BY-SA 2.5
2011-01-05T00:23:19.227Z
2011-01-05T00:38:04.117Z
2011-01-05T00:38:04.117Z
Tsuyoshi Ito
<p>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$.</p>

<p>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)</p>

<p>What if negative weights are allowed?</p>

CC BY-SA 2.5
2011-01-04T22:42:57.007Z
do you want the tree to be arborescence? or undirected tree?
RubyDubee
CC BY-SA 2.5
2011-01-04T22:49:39.823Z
arborescence rooted at $s$
Imran Rauf
CC BY-SA 2.5
2011-01-05T02:23:26.530Z
Please edit your question so that people do not have to read the comments to understand what is being asked.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-05T07:51:51.820Z
Aren't arborescence and directed tree both rooted at $s$ the same thing in DAG.?
Imran Rauf
CC BY-SA 2.5
2011-01-05T09:05:25.227Z
@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
CC BY-SA 2.5
2011-01-05T09:52:07.550Z
@Tsuyoshi: Agreed, I updated the question accordingly.
Imran Rauf
<ds.algorithms><graph-algorithms>
Finding maximum weight arborescence in an edge-weighted DAG
Imran Rauf
# Finding maximum weight arborescence in an edge-weighted DAG

(Asked by: username_0 on 2011-01-04)

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?

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: do you want the tree to be arborescence? or undirected tree?  
> **username_0**: arborescence rooted at $s$  
> **username_2**: Please edit your question so that people do not have to read the comments to understand what is being asked.  
> **username_0**: Aren't arborescence and directed tree both rooted at $s$ the same thing in DAG.?  
> **username_2**: @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.  
> **username_0**: @Tsuyoshi: Agreed, I updated the question accordingly.  

---

## 2 answers

### Answer by username_2 on 2011-01-05. Score: 10 | Accepted answer

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*={*a*1, …, *a**n*} and *C*={*S*1, …, *S**m*} (*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 *x*1, …, *x**m*, each of which has an incoming edge from *s* with weight −1.
* The third layer consists of *n* vertices *y*1, …, *y**n*. The vertex *y**i* has an incoming edge from the vertex *x**j* with weight 0 for each pair (*i*, *j*) such that *a**i*∈*S**j*.
* The fourth layer consists of *n* vertices *z*1, …, *z**n*. Each vertex *z**i* has an incoming edge from the corresponding vertex *y**i* 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*.

> **Comments:**
> **username_4**: Clever! Do you mind if I put it into the [original proof list](http://meta.cstheory.stackexchange.com/q/784/1800)? Or do you think it is at the level of an observation?  
> **username_2**: @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.  
> **username_0**: Many thanks Tsuyoshi for the elegant proof! I had the intution that the problem must be NP-complete, but somehow couldn't prove it.  

---

### Answer by username_3 on 2011-01-04. Score: 0

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.

> **Comments:**
> **username_0**: This works when all edge weights are positive. With negative weight, we may need to discard some of the nodes.  
> **username_3**: Oops ! Got it :-)  

---

