1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you please clarify your problem? I'm not sure I understand the problem you described in the first part of your question, and how it relates to the definition of an oriented spanning tree in the second part of your question. IIRC the definition of a directed multigraph usually has the undirected edges represent two connected edges in opposite directions. Is that the case here? In this case, I'm almost certain what you want is exactly the min-cost arborescence algorithm. $\endgroup$
    – BearAqua the Logician
    Commented Aug 25, 2020 at 17:25
  • $\begingroup$ Also, by "if they are chosen" do you mean once we decide to include the edge in the algorithm, its direction will "magically" be specified via an oracle? If that's the case then we can just trivially query for all edges' directions first in $O(|E|)$-time and then use the min-cost arboresence algorithm. $\endgroup$
    – BearAqua the Logician
    Commented Aug 25, 2020 at 17:27
  • $\begingroup$ After the "if they are chosen" part, I missed a not. $\endgroup$
    – Edward
    Commented Aug 25, 2020 at 17:51
  • $\begingroup$ I know the direction according to other information. The resulted rooted tree should not violate these information. $\endgroup$
    – Edward
    Commented Aug 25, 2020 at 17:56
  • $\begingroup$ Thanks for the quick reply. I think we are talking about the same thing. As for the min-cost arborescence algorithm you mentioned, I found minimum_spanning_arborescence in networkx works for directed multi-graph. It works for this example. I saw the authors are discussing it as well in #3825. $\endgroup$
    – Edward
    Commented Aug 25, 2020 at 18:03

1 Answer 1

Reset to default
0
$\begingroup$

As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.