0 Abstract
This is a very simple and naive survey on M(Minimum) S(Spanning) T(Tree) problem. This problem is a widely researched and extremely important combinatorial problem, which has significant influences on all kinds of fields such as computer architecture allocation, transportation, express logistics, to name but a few. Also, a MST can also provide bounds (lower bound and 2-approximation upper bound if given triangle inequality) for Travelling Salesman Problem. Here I will introduce some classical algorithms and several modern and asymptotically better algorithms as well as parallel algorithms.
1 Introduction
In a network composed of nodes and arcs with costs, a spanning tree is a acyclic subgraph connecting all the nodes together. A minimum spanning tree is the spanning tree with minimum cost on the network. That is it is the spanning tree with the least sum of the costs of all the edges.
Finding the minimum spanning tree is useful is several different applications. Perhaps the most direct application is designing physical systems like road system. For example, consider isolated villages that need to be connected with roads. We need to ensure that each village has at least one way to go to any other villages. Obviously, we also want the total construction cost to be minimum, and this forms a MST problem. We can easily come up with other ideas and situations needing the aid of MST.
Another application of the minimum spanning tree problem is cluster analysis. Suppose that we have a network and want to split the network into k different clusters such that the total cost of all the clusters is minimized. We can take the minimum spanning tree and delete the k−1 arcs with the highest cost. The result is a forest of k trees with minimal cost.
We can see that the above two examples respectively correspond to adding edges and deleting edges. We will then show that both adding and deleting edges are important with respect to MST problem. They are important in finding a MST and using MST to solve a practical problem.
2 Basic Principle
:::info
[Definition 1] Fundamental Cutset
For a graph
two distinct vertices say
and
, let
be any subset of vertices that contains
but not
and let
be its complement, then set
is a
and the set of edges
is called a 
. The removal of the arcs in a 
leaves a disconnected subgraph of
. Corresponding to each edge
of a spanning tree
of a connected graph
, there is a unique cutset called thefundamental cutsetof the tree
with respect to edge
.
:::
We will then show that this definition has much to do with adding edges.
:::info
[Definition 2] Fundamental Circle
Given a graph
, a spanning tree
and a co-tree edge 
, the unique cycle in
consisting of the edge
and the edges of the unique chain in
between
and
is called
afundamental cycleof
relative to
with respect to
.
:::
We will then show that this definition has much to do with deleting edges.
[Theorem 1] Fundamental Cut Optimality A spanning tree
in a weighted graph is a MST if and only if every edge in the tree is a minimum weight edge in the
fundamental cutsetdefined by that edge.
Proof:
the weight of edge
is noted as
.
1’ MST==>Cut Opt: This can be proved by contradiction. Suppose
is a minimum spanning tree violating Cut Opt, then there are two edges
and
such that
. Then replacing 
with
would yield a lower cost spanning tree.
2’ Cut Opt==>MST: Contradiction again. Suppose
satisfies the cut optimality conditions, but
is not a minimum spanning tree. That is, there exists a tree
that is a minimum spanning tree. Then, since
is not a minimum spanning tree, it must have an edge
not contained in
. Deleting edge
from
creates a cut
. Adding one edge to a tree will form and only form one circle. Assume we add
to 
then we will get a circle
. Since
, there must be an edge
in circle
such that
. According to Cut Opt we know that
, and also we have
because
is a MST, which means that if
then we can replace
with
yielding a less cost tree. Having the both inequalities, we know that
. Then we just replace
freely with
making a new MST (the total cost doesn’t change, so it’s still a MST) . Following this process, we can gradually change
into
, which means that
is already a MST.
[Theorem 2] Fundamental Circle Optimality A spanning tree
in a graph
is a MST if and only if every edge
is a maximum weight edge in the unique
fundamental cycledefined by that edge.
Proof:
1’ MST==>Circle Opt: This can also be proved by contradiction. Assume that there exists a MST
violating Fundamental Circle Optimality, which means that there is an edge
weighing less than one edge
in the fundamental cycledefined by
. Then we could delete edge
and add edge
, then we can get a new tree
with less cost. This conflictst with the assumption that
is a MST.
2’ Circle Opt==>MST: This can be proved with the help of Theorem 1. It’s obvious that if a tree doesn’t hold Cut Opt, then it will not hold Circle Opt either. So we know that: Circle Opt==>Cut Opt. Then we have: Circle Opt==>Cut Opt==>MST using Theorem 1.
This is my personal proof, and here is an another much more elegant proof in [1].
Blue Rule: Select a cutset that does not contain a blue edge. Among the uncoloured edges in the cutset, select one of minimum weight and colour it blue.
Red Rule: Select a simple cycle containing no red edges. Among the uncoloured edges on the cycle, select one of maximum weight and colour it red.
These two rules are proposed in Tarjan’s book[3], and elaborately illustrated by tutorial slides[2]. Since we already proved these two optimality conditions, these two rules can be immediately derived.
Both red rules and blue rules can be used for the construction of MST, but in practice, we usually use blue rule. The most well known algorithms including Prim, Kruskal and Sollin’s algorithm are all using blue rule.
3 Details of Classical Algorithm
3.1 Sollin’s (Boruvka’s) Algorithm
More commonly known as Boruvka’s algorithm, Sollin’s algorithm was the first algorithm for the minimum spanning tree problem. Borukva first published his algorithm in 1926 which he designed as a way of constructing an efficient electricity network in Moravia, a region of the Czech Republic. He published two papers in the same year with this algorithm. One was 22 pages and has been viewed as unnecessarily complicated. The other was a one page paper that has been regarded as the key paper showing Boruvka’s understanding and knowledge of the problem.
It was then independently rediscovered in 1938 by French mathematician Gustave Choquet, and finally rediscovered in 1962 by Georges Sollin.
We have introduced this algorithm in our lectures, so here I will not elaborately illustrate it. Each time we choose an edge with lowest cost from all edges incident to a component. We then add these edges into the graph and form a new graph with less components. It’s obvious that this algorithm is using blue rules to add edges.
The time complexity is
.
3.2 Prim Algorithm
This algorithm is so classical that almost everyone will be taught with this algo when learning MST for the first time. It use an arbitrary starting vertex
and apply the color step
times. The color step is that: Let
be the blue tree containing the vertex
. Select a minimum weight edge incident to
and colour it blue.
There are many ways to implement Prim algorithm, with different time complexity. The difference lies in the way we select the minimum-weight edge. If we simply go through all the edges, then the time complexity would be
. If we use binary heap and adjacent list, the time complexity would be
. If we use Fibonacci heap, the time complexity would be
. If we use d-heap, which is a general case of binary heap and an implementation of priority queue, the time complexity would be
. If we properly choose
, we can always get a satisfying algorithm for both dense graph and sparse graph (if dense, use a large d; if sparse, use a small d).
3.3 Kruskal Algorithm
This algorithm is easy to implement and very suitable for competitive programming contests, so many competitors are very familiar with this algorithm. And its algorithm process can be a proof to many properties. The time complexity is
. This algorithm is also using blue rule, each time picking up the minimum-weight edge. If the edges are already sorted for us, then the time complexity could be
, where
is the inverse Ackermann’s function. This is because we are using union-and-find. To be honest, I didn’t understand the proof of the time complextiy of union-and-find, here I’m just using the result provided by Wikipedia.
4 Not That Well-Known Algorithm
We learned two not that well-known algorithms in this class: Yao algorithm and Cheriton-Tarjan algorithm. They are adapted from Sollin’s algorithm, using smarter way to select the minimum-weight edge.
4.1 Yao Algorithm
This is an algorithm proposed by Qizhi Yao. It is on the basis of another algorithm finding the median with deterministic linear time[8]. Assume that we already know how to find the median in linear time, then we can refine Sollin’s algorithm by grouping edges. In Sollin’s, we need to go through every edge to find the one with minimum weight. However, we know that some edges with large weight should not be considered in the early stages.
Consider dividing all the edges into
groups, then we each time only need to go through the edges within the group. Then the time complexity is
. Then what is the time complexity of dividing edges into
groups such that edges in
group have larger weight than these in
group? We each time find the median and divide the set into two parts, and then recurssively go down in these two smaller subset. It’s obvious that the dividing time is
. Then using simple calculus knowledge we can that when
the formula
gets its minimum:
.
4.2 Cheriton-Tarjan Algorithm
The full algorithm[5] is very complex, here is the key point: A heap is kept for each blue tree. Each heap holds the edges with at least one endpoint in the tree and which are candidates for becoming blue. Similar to Kruskal’s algorithm, it grows a spanning forest, beginning with a forest of
components each consisting of a single node. Since, every component
must eventually be connected to another component, this algorithm keeps a separate heap
for each component
, so, that initially
smaller heaps are used. Initially,
will contain only
edges, since
consists only of vertex
. When
and
are merged,
and
must also be merged. This requires a modification of the data structures, since heaps cannot be merged efficiently. This is essentially because merging heaps reduces to building a new heap. It’s difficult to work out the precise time complexity, I still need some time to understand the original paper. Here I just use the result provided by the paper, that the time complexity is
.
In Cheriton and Tarjan’s paper, they also proposed an algorithm for planar graph with time complexity
, and an algorithm for sparse graph with time complexity
.
5 Randomized Algorithm
5.1 Tarjan’s Expected Linear Time Algorithm
It was developed by David Karger, Philip Klein, and Robert Tarjan. So it is also known as Karger’s algorithm. The algorithm relies on techniques from Boruvka’s algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.
The key insight to the algorithm is a random sampling step which partitions a graph into two subgraphs by randomly selecting edges to include in each subgraph. The algorithm recursively finds the minimum spanning forest of the first subproblem and uses the solution in conjunction with a linear time verification algorithm to discard edges in the graph that cannot be in the minimum spanning tree. A procedure taken from Borůvka’s algorithm is also used to reduce the size of the graph at each recursion.
In more details, there are three steps in total: Boruvka step, random sampling step, and verification step.
- Boruvka Step: Given a graph
, apply the Boruvka algorithm to carry out one coloring step only. And then contract the graph
and get
. - Random sampling step: Given a contracted graph
, choose a subgraph
by selecting each edge
in
independently with a probability
.
- Verification step: Given any minimum spanning forest
of
, find the
edges and delete them from
to reduce the graph further. Here
means that the weight of an edge
is larger than the weight of the path from
to
in a forest
. It’s obvious that all the
edges will not appear in the final MST, so we can delete them.
The complete algorithm process is shown below:
- Given
, apply two successive Boruvka steps to the graph to contract
. - Apply the random sampling step to the contracted graph to select
. - Apply the algorithm recursively producing a minimum spanning forest
of the
formed in step 1 - Given
of
, apply the verification step to the subgraph
, which was chosen, and obtain
a graph
which is reduced further.
- Apply the algorithm recursively to
to compute the minimum spanning forest
of
. - Return those edges contracted in step 1 together with the edges of
.
The time complexity relies on two properties:
Property 1 Let
be a subgraph obtained from
by including each edge independently with probability
, and let
be the minimum spanning forest of
. The expected number of
edges in
is at mos
where
is the number of vertices.
Property 2 We can do the verification step in deterministic linear time with the algorithm[9] proposed by V. King.
Both properties need further research and more time, I will get it through soon.
The expected running time is
and it runs in
time with probability
.
In the worst case, it will be equivalent to Boruvka’s algorithm, so the worst time complexity is
.
6 Parallel Algorithms
The performance comparison of these sequencial algorithms is basically of no use, because in reality, we will never use one processer to handle a large-scale problem. And this is also the reason why parallel algorithms are getting more and more popular. All the classical algorithms illustrated above can be adapted into parallel version.
6.1 Prim Parallel Version
Prim algorithm has the least parallelism possiblity. Because each time we need to update the distance vecter, which can’t be paralleled, since each element can’t be changed by two processes. What we can do is that: we can use paralleled priority queue with insert time complexity of
.
6.2 Kruskal Parallel Version
There are two ways to parallelize the Kruskal algorithm. The first is to parallelize the sorting stage. We know that in Kruskal algorithm, we need to sort all the edges by their weight, which could be parallelized. We can sort
elements in
time with
processors. So the total time would be
. The second way is to parallelize an adaptation of Kruskal algorithm, which is named Filter-Kruskal algorithm[10].
6.3 Sollin Parallel Version
In Sollin’s process, we have three stages. The first stage is finding the lightest edge, which can be parallelized; the second stage is to go through each subgraph, which can be parallelized; the third stage is to contract the graph, which can be parallelized. The respective time complexity is
.
7 Other Applicatioins and Properties
There are so many different variations about MST, coming up with different graceful properties. We can impose some edges, which means that these edges must be in MST, and then construct the MST; We can add a new vertex and the incident edges and find the new MST based on the previous MST, which is one of our homework problems; We can delete one vertex and find the new MST; We can change the weight of one edge and find the MST; We can get linear time approxiamations on MST, to name but a few.
Here I will introduce some simple properties:
- Given a graph with its MST, and a new vertex with its incident edges, we can find the new MST in
time. This is based the observation: the new MST will only contain the newly added edges and the edges in the original MST. - Given a graph with its MST, and a deleted vertex, we can also ensure that the new MST will consist all the edges in the previous MST except for these deleted ones.
- Add a constant to the weight of every vertex will not change the MST.
- Change the weight of an edge, there are four cases in total. If we decrease the edge in MST, remains the same; If we increase the edge not in MST, remains the same; If we increase the edge in MST, we just need
time to find the new edge connecting the two components; If we decrease the edge not in MST, we just need to find the circle in
, if the decreased weight is smaller than any edge in that circle, we can do a substitution. - There might be many MSTs in a graph, but all the MSTs have the same edges-weight-set, which means that: if we only focus on the weight of the edges in MST, then the sorted array of the weights of the edges in any MST is the same.
8 Reference
[1] Slides about MST and cut optimality and path optimality conditions https://copland.udel.edu/~amotong/teaching/algorithm%20design/lectures/(Lec%2012)%20Greedy%20Strategy%20-%20Minimum%20Spanning%20Tree%20-%20Optimality%20Condition.pdf%20Greedy%20Strategy%20-%20Minimum%20Spanning%20Tree%20-%20Optimality%20Condition.pdf)
[2] Slides about MST and blue rule and red rule
https://www.cs.princeton.edu/~wayne/cs423/lectures/mst.pdf
[3] Tarjan RE. Data structures and network algorithms. In CBMS-NFS Regional Conference Series in Applied Mathematics. Philadelphia: Society for Industrial and Applied Mathematics, 1983. p. 44.
https://www.amazon.com/Structures-Algorithms-CBMS-NSF-Conference-Mathematics/dp/0898711878
(This is a book, so it’s the link of the book on Amazon)
[4] Johnson DB. Priority queues with update and “finding minimum spanning trees. Information Processing Letters 1975;4:53}7.
https://www.sciencedirect.com/science/article/abs/pii/0020019075900010
ZJU didn’t subscribe to this journel, pity.
[5] FINDING MINIMUM SPANNING TREES, DAVID CHERITON AND ROBERT ENDRE TARJAN
https://epubs.siam.org/doi/pdf/10.1137/0205051
[6] Improved Multiple Constant Multiplication Using a Minimum Spanning Tree
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1399088
[7] Imposing edges in Minimum Spanning Tree
https://arxiv.org/pdf/1912.09360.pdf
[8] Linear Time Median Finding: https://rcoh.me/posts/linear-time-median-finding/
[9] A Simpler Minimum Spanning Tree Verification Algorithm
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/A%20Simpler%20Minimum%20Spanning.pdf
[10] The Filter-Kruskal Minimum Spanning Tree Algorithm
http://algo2.iti.kit.edu/documents/fkruskal.pdf
若有收获，就点个赞吧
0 人点赞
