# 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. Mar 30, 2012 at 10:45
• Whether such a thing exists depends crucially on your definitions. Mar 30, 2012 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, also known as the arborescence problem (PDF). 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? :) Mar 31, 2012 at 7:19
• First link is broken Oct 31, 2019 at 16:35
• The Chu-Liu/Edmonds algorithm requires specifying a single root whereas spanning trees do not specify a root. There is nothing about directed graphs, whether cyclic or acyclic, that inherently constrains one to minimum solution with a single root, let alone that the root(s) is(are) givens. Jul 27, 2021 at 17:41
• @wanderingmathematician I checked the Wayback machine and that link has unfortunately been broken since it was first archived way back in 2015. I found some PDF lecture notes to link instead. Oct 25, 2021 at 19:14

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. Nov 4, 2019 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. Nov 4, 2019 at 9:29