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
sin 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
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
von a directed multigraph
G, an oriented spanning tree
vis an acyclic subgraph of
Gin which every vertex other than
vhas 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.