# Does spanning tree make sense for DAG?

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.

• Please flesh out the question a bit. Why do you think the usual definition does not make sense? Of course, you will have to decide wether the spanning three should have directed paths from a root to all nodes or not; that might make a difference. – Raphael Mar 30 '12 at 10:45
• Whether such a thing exists depends crucially on your definitions. – Dave Clarke Mar 30 '12 at 10:53

Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem. The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.

• Maybe you should edit the Wiki article? :) – Raphael Mar 31 '12 at 7:19
• First link is broken – wanderingmathematician Oct 31 at 16:35

One generalization of a tree in a directed graph is an arborescence. It is a directed tree with all edges directed from parent to child.

• What about some sort of Minimum Spanning Forest? I don't see a problem with making an MST for each root. – Radio Controlled Nov 4 at 9:28

The case for DAGs is trivial, which might be the reason you cannot find any dedicated information about them.

First, there must be a unique vertex $r$ of zero incoming degree, which is the root of the directed spanning tree (arborescence). (Otherwise no spanning tree can exist.)

Next, for each vertex $v \neq r$ choose a parent vertex $P(v)$ such that the $w(v, P(v))$ is minimal.

We chose $|V| - 1$ edges in a graph of $|V|$ vertices with no cycles, so thus chosen subset of edges forms a spanning tree $T$. Any other spanning tree, for each vertex $v \neq r$, must have a unique incoming edge $(v, Q(v))$. By our construction $w(v, P(v)) \leq w(v, Q(v))$. Summing over all $v \neq r$ we get that $T$ is minimal.

• What about some sort of Minimum Spanning Forest? I don't see a problem with making an MST for each vertex of zero incoming degree. – Radio Controlled Nov 4 at 9:29