1

So for MST there are 2 possible definitions in an undirected graph. Keep in mind that in an undirected graph the MST algorithm always has n - 1 edges and no cycles. In an undirected graph, it doesn't matter which definition you use, since both are correct, however inside a directed graph thats not the case anymore. Definitions:

  1. Choosing a root vertex u in a graph, the MST is the smallest cost tree which connects every other vertex from u.
  2. Given a graph, the minimal cost subgraph which connects all nodes is called a MST. (In an undirected graph this must be a tree)

In a directed graph the first definition for a directed graph is arborescence. However the arborescence is different with every vertex you choose (This is not the case in an undirected graph), resulting in multiple possible directed MST variations. In the links section i have a video which explains the def. of an arborescence.

The second definition requires the directed graph to be one big strongly connected component. Hence it is now possible to go from any vertex u to any other vertex v, there is only 1 MST in a directed graph. However now we are not talking about trees anymore, hence the MST must include cycles. In the links section i included a graph as example for the second definition. In this image there are more then 1 possible minimum graphs, one for either of the red edges removed for example.

My question is, what is second definition called in a directed graph? (Does it have a special name like arborescence) and if so, isn't that the directed variant of MST? Is there an algorithm to compute the minimum graph inside a strongly connected component?

Definition of arborescence on Wikipedia

Quick video explaining what an arborescence is

I created a graph example of what i mean with the second definition:

enter image description here

  • Yet another vocabulary lesson. – Robert Harvey Jan 2 '15 at 17:43
  • The language barrier really is hard sometimes, isn't it. My question simply put is: What is the minimum cost graph inside a strongly connected component, which connects every vertex with every other vertex. – user2035546 Jan 2 '15 at 17:44
0

Alright so the problem is called MSSS and is NP-Complete, i got pointed to the following stackoverflow discussion, which talks about this problem: https://stackoverflow.com/questions/1536067/minimum-cost-strongly-connected-digraph

However i still like the discussion about which of these problems: MSSS vs Arborescence can be considered the inverse of MST.

So to answer my own question i have listed a few points for each of them (please comment if otherwise).

  1. MST is a tree, only the Arborescence returns a tree. (+1 Arborescence)
  2. MSSS only has one correct answer, as the MST does, it doesn't need any central points. (+1 MSSS)

Conclusion: Neither of these, MSSS or Arborescence can be called the directed version of MST, without talking about the other problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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