# Oriented spanning tree of a directed multi-graph I have problem of inferring a rooted tree out of a connected simple graph.

The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of condition:

• There is a known root, which is `s` in the following example.
• We know directions of some edges if they are chosen. These edges are not chosen yet, or the problem becomes a Steiner tree problem.

Note that numbers on edges are their weights. So we will get `s -> b -> c -> a` if a normal min spanning tree is applied, but the direction of edge `ac` is wrong. On the other hand, we cannot use Chu–Liu/Edmonds’ algorithm for spanning arborescence of directed graphs, because we don’t know and cannot infer the direction of edge `bc`. We can infer some edges’ directions according to the position of the root. For example, in the example, we know `s -> b` and `s -> a`.

It seems that the problem can be solved by two steps:

1. turn the simple graph into a multi-graph. For edges (in the original simple graph) whose directions are unknown, we represent them in a multi-graph using two directed edges between two vertices with inverse directions.
2. We find the minimum oriented spanning tree of this multi-graph.

## Oriented Spanning Tree

In the final section of spanning tree, Wikipedia, oriented spanning tree is mentioned and a paper (levine2011sandpile) is referred. The problem fits the setting. It says:

Given a vertex `v` on a directed multigraph `G`, an oriented spanning tree `T` rooted at `v` is an acyclic subgraph of `G` in which every vertex other than `v` has outdegree 1.

Note that the term “outdegree” is a bit confusing, which I think should be “indegree”. But it doesn’t matter, because it just restricts the simple subgraph to be a directed tree with root being source or sink.

But it is not clear to me how an algorithm can be implemented according to that paper. Posted on Categories Articles