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
sin 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
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
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.
For edges (in the original simple graph) whose directions are unknown, we add 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.