Oriented spanning tree of a directed multi-graph with minimum weight

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 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.
  • https://en.wikipedia.org/wiki/Spanning_tree

Spanning tree in a graph of intersecting sets

Consider $ n$ sets, $ X_i$ , each having $ n$ elements or fewer, drawn among a set of at most $ m \gt n$ elements. In other words $ $ \forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\right| \le m$ $

Consider the complete graph $ G$ formed by taking every $ X_i$ as a node, and weighing every edge $ (i,j)$ by the cardinal of the symmetric difference $ X_i \triangle X_j$ .

An immediate bound on the weight of the minimal spanning tree is $ \mathcal{O}(n^2)$ , since each edge is at most $ 2 n$ , but can we refine this to $ \mathcal{O}(m)$ ?

For illustration, consider $ 2 p$ sets, $ p$ of which contain the integers between $ 1$ and $ p$ and $ p$ of which contain the integers of between $ p+1$ and $ 2p$ . A minimal spanning tree has weight $ p$ but a poorly chose tree on this graph would have weight $ (p-1)p$ . Intuitively, if there are only $ m$ values to chose from, the sets can’t all be that different from one another.

Prove: If $T’$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $ T’=(V,F’)$ is not a MST of $ G=(V,E)$ , then there are edges $ e’ \in F$ and $ e \in $ $ E$ \ $ F$ such that $ w(e)<w(e’)$ and $ T’$ \ $ \{e’\} \cup \{e\}$ is a spanning tree.

My idea:

Let $ T=(V,F)$ be a MST of $ G$

for all $ e \in T$ , try to insert it into $ T’$ and see if there is an edge in the cycle created that is heavier than $ e$ . If we found such $ e$ we are done.

If not, define $ G’=(V,F \cup F’)$

This graph obviously has a MST.

We didn’t find a suitable $ e$ in the previous part so all edges in $ F$ may be colored in red.

That means there is a MST $ T”=(V,F”)$ such that $ F” \ F’$ but that is impossible because $ T’$ is not a MST of $ G’$ , because $ T$ is lighter.

Does that seem correct?

Data structure implementation of MST (Minimum spanning tree) through Fibonacci heaps

How can a fibonacci heap store the information needed by the algorithm? In order to achieve good efficiency, when would you run the Consolidate routine?

Algorithm :

MST(G) 2 T ← {} // set that will store the edges of the MST 3 for i ← 1..n 4 Vi ← {i} 5 Ei ← {(i, j) : j is a vertex and (i, j) is an edge of G} // set of all edges incident with vertex i 6 end for 7 while there is more than one set Vi 8 choose any Vi 9 extract minimum weight edge (u, v) from Ei 10 one of the endpoints u of this edge is in Vi ; let Vj be the set that contains the other endpoint v 11 if i 6= j then 12 T ← T ∪ {(u, v)} 13 combine Vi and Vj into Vi (destroying Vj ) 14 combine Ei and Ej into Ei (destroying Ej ) 15 end if 16 end while 17 return T 18 end MST 

Would you have to add any additional fields to nodes in the heaps or use any additional data structures?

Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $ x$ and $ y$ is it possible to make a faster algorithm than Prim’s algorithm or Kruskal’s algorithm?

I saw on Kruskal’s algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don’t think there is any benefit, but I am not sure…

Variation to spanning tree called Group Spanning Tree

Suppose we have a complete graph with say 100 nodes. We divide the nodes in the graphs into groups for example 10 nodes in each group identified by color. We want to obtain an optimal spanning tree that operates under the constraint that at least one node will be present from each group. The resulting spanning tree can be called a group spanning tree. How to write an efficient algorithm for this making sure it is a tree(no cycles) and not looping over the entire node set on every pass to check presence of cycles and also making sure at least one node from each group is represented.

Graph with exactly 2 Minimum Spanning Trees

Say that a graph, $ G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in of the 2 MSTs) that at minimum, 2 of the edges in the set which is the union of the edges have equal weight. Also show that either this edge is the largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can’t be distinct, otherwise there wouldn’t be multiple MSTs. Also the graph $ G$ must contain cycles, otherwise, it wouldn’t have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $ MST_1$ there is some edge, $ e$ that is not in $ MST_2$ and there is also some edge $ f$ that is not in $ MST_1$ . Using the cut property if $ e$ was not placed in $ MST_2$ and $ f$ was not placed in $ MST_1$ then then we have that the weight of $ f$ , and $ e$ , $ w(f) = w(e)$ .

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that’s actually true. Then from there I felt that there had to be some node, $ z$ such that $ z$ had 2 edges with the same weights, and when we combine the edges from $ MST_1$ and $ MST_2$ we end up with both the edges from $ z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle… Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $ G$ , in order for it to have exactly 2 MSTs? Or is there some property I’m missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.

How can Kruskal’s algorithm return different spanning trees?

We assume that we have the same graph G.

In introduction to Algorithms by Cormen it’s said that it`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

Suppose that A is an empty set of edges. Then, make any cut that has (u, v) crossing it. Then, since that edge is of minimal weight, we have that (u, v) is a light edge of that cut, and so it is safe to add. Since we add it, then, once we finish constructing the tree, we have that (u, v) is contained in a minimum spanning tree.

What does it mean to make a cut? I`m familiar with Kruskal’s algorithm but nowhere in the process do I see cuts being made. It’s either we unite two trees and add the edge to A or we reject the edge and continue on.