5
$\begingroup$

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

$\endgroup$
2
  • 8
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Mar 30, 2012 at 10:45
  • 8
    $\begingroup$ Whether such a thing exists depends crucially on your definitions. $\endgroup$ Mar 30, 2012 at 10:53

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ Maybe you should edit the Wiki article? :) $\endgroup$
    – Raphael
    Mar 31, 2012 at 7:19
  • 1
    $\begingroup$ First link is broken $\endgroup$ Oct 31, 2019 at 16:35
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2021 at 17:41
  • $\begingroup$ @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. $\endgroup$
    – Oliphaunt
    Oct 25, 2021 at 19:14
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What about some sort of Minimum Spanning Forest? I don't see a problem with making an MST for each root. $\endgroup$ Nov 4, 2019 at 9:28
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 4, 2019 at 9:29

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.