Solved. This is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).

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.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

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.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

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.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

Solved. This is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).

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.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

I have problem of finding the minimum spanning tree of a simple graph, 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 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.

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.

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. Then we find the oriented spanning tree of this multi-graph.

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

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

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.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree