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**:

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