An optimal minimum spanning tree algorithm.
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning tree of a graph with n vertices and m edges that runs in time O(T*(m,n)) where T* is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine.Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T* are (m) and O(m  (m,n)), where  is a certain natural inverse of Ackermann's function.Even under the assumption that T* is superlinear, we show that if the input graph is selected from Gn,m, our algorithm runs in linear time with high probability, regardless of n, m, or the permutation of edge weights. The analysis uses a new martingale for Gn,m similar to the edge-exposure martingale for Gn,p.
Introduction
The minimum spanning tree (MST) problem has been studied for much of this century and
yet despite its apparent simplicity, the problem is still not fully understood. Graham and Hell
[GH85] give an excellent survey of results from the earliest known algorithm of Boruvka [Bor26]
to the invention of Fibonacci heaps, which were central to the algorithms in [FT87, GGST86].
Chazelle [Chaz97] presented an MST algorithm based on the Soft Heap [Chaz98] having complexity
O(m(m;n) log (m; n)), where  is a certain inverse of Ackermann's function. Recently Chazelle
[Chaz00] modied the algorithm in [Chaz97] to bring down the running time to O(m  (m; n)).
Later, and in independent work, a similar algorithm of the same running time was presented in
Pettie [Pet99], which gives an alternate exposition of the O(m  (m; n)) result. This is the tightest
time bound for the MST problem to date, though not known to be optimal.
This is an updated version of UTCS Technical Report TR99-17 which includes performance analysis on random
graphs and new references. Part of this work was supported by Texas Advanced Research Program Grant 003658-
0029-1999. Seth Pettie was also supported by an MCD Fellowship.
All algorithms mentioned above work on a pointer machine [Tar79] under the restriction that
edge weights may only be subjected to binary comparisons. If a more powerful model is assumed,
the MST can be computed optimally. Fredman and Willard [FW90] showed that on a unit-cost
RAM where the bit-representation of edge weights may be manipulated, the MST can be computed
in linear time. Karger et al. [KKT95] presented a randomized MST algorithm that runs in linear
time with high probability, even if edge weights are only subject to comparisons.
It is still unknown whether these more powerful models are necessary to compute the MST
in linear time. However, in this paper we give a deterministic, comparison-based MST algorithm
that runs on a pointer machine in O(T  (m; n)) time, where T  (m; n) is the number of edge-weight
comparisons needed to determine the MST on any graph with m edges and n vertices. Additionally,
we show that our algorithm runs in linear time for the vast majority of graphs, regardless of density
or the permutation of edge weights.
Because of the nature of our algorithm, its exact running time is not known. This might seem
paradoxical at rst. The source of our algorithm's optimality, and its mysterious running time, is the
use of precomputed 'MST decision trees' whose exact depth is unknown but nonetheless provably
optimal. A trivial lower bound on our algorithm is
m); the best upper bound, O(m(m;n)),
is due to Chazelle [Chaz00]. We should point out that precomputing optimal decision trees does
not increase the constant factor hidden by big-Oh notation, nor does it result in a non-uniform
algorithm.
Our optimal MST algorithm should be contrasted with the complexity-theoretic result that any
optimal verication algorithm for some problem can be used to construct an optimal algorithm
for the same problem [Jo97]. Though asymptotically optimal, this construction hides astronomical
constant factors and proves nothing about the relationship between algorithmic complexity and
decision-tree complexity. See Section 8 for a discussion of these and other related issues.
In the next section we review some well-known MST results that are used by our algorithm.
In section 3 we prove a key lemma and give a procedure for partitioning the graph in an MST-
respecting manner. Section 4 gives an overview of the optimal algorithm and discusses the structure
and use of pre-computed decision-trees for the MST problem. Section 5 gives the algorithm and
a proof of optimality. Section 6 shows how the algorithm may be modied to run on a pointer
machine. In section 7 we show our algorithm runs in linear-time w.h.p. if the input graph is
selected at random. Sections 8 & 9 discuss related problems and algorithms, open questions, and
the actual complexity of MST.
Preliminaries
The input is an undirected graph E) where each edge is assigned a distinct real-valued
weight. The minimum spanning forest (MSF) problem asks for a spanning acyclic subgraph of
G having the least total weight. In this paper we assume for convenience that the input graph
is connected, since otherwise we can nd its connected components in linear time and then solve
the problem on each connected component. Thus the MSF problem is identical to the minimum
spanning tree problem.
It is well-known that one can identify edges provably in the MSF using the cut property, and
edges provably not in the MSF using the cycle property. The cut property states that the lightest
edge crossing any partition of the vertex set into two parts must belong to the MSF. The cycle
property states that the heaviest edge in any cycle in the graph cannot be in the MSF.
2.1 Boruvka steps
The earliest known MSF algorithm is due to Boruvka [Bor26]. The algorithm is quite simple: It
proceeds in a sequence of stages, and in each stage it executes a Boruvka step on the graph G, which
identies the set F consisting of the minimum-weight edge incident on each vertex in G, adds these
edges to the MSF (since they must be in the MSF by the cut property), and then forms the graph
as the input to the next stage, where GnF is the graph obtained by contracting each
connected component formed by F . This computation can be performed in linear time. Since
the number of vertices reduces by at least a factor of two, the running time of this algorithm is
O(m log n), where m and n are the number of vertices and edges in the input graph.
Our optimal algorithm uses a procedure called Boruvka2(G; F; G 0 ). This procedure executes
two Boruvka steps on the input graph G and returns the contracted graph G 0 as well as the set of
edges F identied for the MSF during these two steps.
2.2 Dijsktra-Jarnk-Prim Algorithm
Another early MSF algorithm that runs in O(m log n) time is the one by Jarnk [Jar30], re-discovered
by Dijkstra [Dij59] and Prim [Prim57]. We will refer to this algorithm as the DJP algorithm. Brie
y,
the DJP algorithm grows a tree T , which initially consists of an arbitrary vertex, one edge at a
time, choosing the next edge by the following simple criterion: Augment T with the minimum
weight edge (x; y) such that x 2 T and y 62 T . By the cut property, all edges in T are in the MSF.
Lemma 2.1 Let T be the tree formed after the execution of some number of steps of the DJP
algorithm. Let e and f be two arbitrary edges, each with exactly one endpoint in T , and let g be the
maximum weight edge on the path from e to f in T . Then g cannot be heavier than both e and f .
Proof: Let P be the path in T connecting e and f , and assume the contrary, that g is the heaviest
edge in P [ fe; fg. Now consider the moment when g is selected by DJP and let P 0 be the portion
of P present in the tree. There are exactly two edges in (P P which are eligible to
be chosen by the DJP algorithm at this moment, one of which is the edge g. If the other edge is
in P then by our choice of g it must be lighter than g. If the other edge is either e or f then by
our assumption it must be lighter than g. In both cases g could not be chosen next by the DJP
algorithm, a contradiction. 2
2.3 The Dense Case Algorithm
The algorithms presented in [FT87, GGST86, Chaz97, Chaz00, Pet99] will nd the MSF of a graph
in linear time if the graph is su-ciently dense, i.e., has a su-ciently large edge-to-vertex ratio. For
our purposes, 'su-ciently dense' will mean
an (3) n), where n is the number of vertices in the
graph. All of the above algorithms run in linear time for that density.
The procedure DenseCase(G; F ) takes as input an n-node graph G and returns the MSF F of
G in linear time for graphs with
density
263 (3) n).
Our optimal algorithm will call DenseCase on a graph derived from an n-node, m-edge graph
by contracting vertices so that the number of vertices is reduced by a factor
of
n). The
number of edges in the contracted graph is no more than m. It is straightforward to see that
DenseCase will run in O(m + n) time on such a graph.
2.4 Soft Heap
The main data structure used by our algorithm is the Soft Heap [Chaz98]. The Soft Heap is a kind
of priority queue that gives us an optimal tradeo between accuracy and speed. It supports the
following operations:
MakeHeap(): returns an empty soft heap.
Insert(S; x): insert item x into heap S.
Findmin(S): returns item with smallest key in heap S.
delete x from heap S.
create new heap containing the union of items stored in S 1
and S 2 , destroying S 1 and S 2 in the process.
All operations take constant amortized time, except for Insert, which takes O(log( 1
To
save time the Soft Heap allows items to be grouped together and treated as though they have a
single key. An item adopts the largest key of any item in its group, corrupting the item if its new
key diers from its original key. Thus the original key of an item returned by Findmin (i.e. any
item in the group with minimum key) is no more than the keys of all uncorrupted items in the
heap. The guarantee is that after n Insert operations, no more than n corrupted items are in the
heap. The following result is shown in [Chaz98].
Lemma 2.2 Fix any parameter 0 <  < 1=2, and beginning with no prior data, consider a mixed
sequence of operations that includes n inserts. On a Soft Heap the amortized complexity of each operation
is constant, except for insert, which takes O(log(1=)) time. At most n items are corrupted
at any given time.
3 A Key Lemma and Procedure
3.1 A Robust Contraction Lemma
It is well known that if T is a tree of MSF edges, we can contract T into a single vertex while
maintaining the invariant that the MSF of the contracted graph plus T gives the MSF for the
graph before contraction.
In our algorithm we will nd a tree of MSF edges T in a corrupted graph, where some of the
edge weights have been increased due to the use of a Soft Heap. In the lemma given below we show
that useful information can be obtained by contracting certain corrupted trees, in particular those
constructed using some number of steps from the Dijkstra-Jarnik-Prim (DJP) algorithm. Ideas
similar to these are used in Chazelle's 1997 algorithm [Chaz97], and more explicitly in the recent
algorithms of Pettie [Pet99] and Chazelle [Chaz00].
Before stating the lemma, we need some notation and preliminary concepts. Let V (G) and
E(G) be the vertex and edge sets of G, and n and m be their cardinality, respectively. Let the
G-weight of an edge be its weight in graph G (the G may be omitted if implied from context).
For the following denitions, M and C are subgraphs of G. Denote by G * M a graph derived
from G by raising the weight of each edge in M by arbitrary amounts (these edges are said to be
corrupted). Let MC be the set of edges in M with exactly one endpoint in C. Let GnC denote
the graph obtained by contracting all connected components induced by C, i.e. by replacing each
connected component with a single vertex and reassigning edge endpoints appropriately.
We dene a subgraph C of G to be DJP-contractible if after executing the DJP algorithm on
G for some number of steps, with a suitable start vertex in C, the tree that results is a spanning
tree for C.
Lemma 3.1 Let M be a set of edges in a graph G. If C is a subgraph of G that is DJP-contractible
w.r.t. G * M , then MSF (G) is a subset of MSF (C) [ MSF (GnC MC ) [ MC .
Proof: Each edge in C that is not in MSF(C) is the heaviest edge on some cycle in C. Since that
cycle exists in G as well, that edge is not in MSF(G). So we need only show that edges in GnC
that are not in MSF(GnC MC are also not in MSF(G).
hence we need to show that no edge in H MSF (H) is in MSF (G). Let
e be the heaviest edge on some cycle  in H (i.e. e 2 H MSF (H)). If  does not involve the
vertex derived by contracting C, then it exists in G as well and e 62 MSF (G). Otherwise,  forms
a path P in G whose end points, say x and y, are both in C. Let the end edges of P be (x; w) and
included no corrupted edges with one end point in C, the G-weight of these edges
is the same as their (G * M)-weight.
Let T be the spanning tree of C * M derived by the DJP algorithm, Q be the path in T
connecting x and y, and g be the heaviest edge in Q. Notice that P [ Q forms a cycle. By our
choice of e, it must be heavier than both (x; y) and (w; z), and by Lemma 2.1, the heavier of (x; y)
and (w; z) is heavier than the (G * M)-weight of g, which is an upper bound on the G-weights of
all edges in Q. So w.r.t. G-weights, e is the heaviest edge on the cycle P [ Q and cannot be in
MSF (G). 2
3.2 The Partition Procedure
Our algorithm uses the Partition procedure which is given below. This procedure nds DJP-
contractible subgraphs C in which edges are progressively being corrupted by the Soft
Heap. Let MC i contain only those corrupted edges with one endpoint in C i at the time it is
completed.
Each subgraph C i will be DJP-contractible w.r.t a graph derived from G by several rounds of
contractions and edge deletions. When C i is nished it is contracted and all incident corrupted
edges are discarded. By applying Lemma 3.1 repeatedly we see that after C i is built, the MSF of
G is a subset of
MSF
The Partition procedure is shown in Figure 1. The arguments appearing before the semicolon
are inputs; the others are outputs. M is a set of edges and C=fC is a set of subgraphs of
G. No edge will appear in more than one of M;C
Initially, Partition sets every vertex to be live. The objective is to convert each vertex to dead,
signifying that it is part of a component C i with  maxsize vertices and part of a conglomerate
of  maxsize vertices, where a conglomerate is a connected component of the graph
Intuitively a conglomerate is a collection of C i 's linked by common vertices. This scheme for
growing components is similar to the one given in [FT87].
We grow the C i 's one at a time according to the DJP algorithm, except that we use a Soft
Heap. A component is done growing if it reaches maxsize vertices or if it attaches itself to an
existing component. Clearly if a component does not reach maxsize vertices, it has linked to a
Partition(G;
All vertices are initially "live"
While there is a live vertex
Increment i
live vertex
Create a Soft Heap consisting of v's edges (uses )
While all vertices in V i are live and jV i j < maxsize
Repeat
Find and delete min-weight edge (x; y) from Soft Heap
Until y
If y is live then insert each of y's edges into the Soft Heap
all vertices in V i to be dead
be the corrupted edges with one endpoint in V i
Dismantle the Soft Heap
Let C := fC z is the subgraph of G induced by V z
Exit.

Figure

1: The Partition Procedure.
conglomerate of at least maxsize vertices. Hence all its vertices can be designated dead. Upon
completion of a component C i , we discard the set of corrupted edges with one endpoint in C i .
The running time of Partition is dominated by the heap operations, which depend on . Each
edge is inserted into a Soft Heap no more than twice (once for each endpoint), and extracted no
more than once. We can charge the cost of dismantling the heap to the insert operations which
created it, hence the total running time is O(m log( 1
)). The number of discarded edges is bounded
by the number of insertions scaled by , thus jM j  2m. Thus we have
Lemma 3.2 Given a graph G, any 0 <  < 1
2 , and a parameter maxsize, Partition nds edge-disjoint
subgraphs
a) For all
b) For all i, jV (C i )j  maxsize.
c) For each conglomerate P 2
d) jE(M)j  2  jE(G)j
4 Overview of the Optimal Algorithm
Here is an overview of our optimal MSF algorithm.
In the rst stage we nd DJP-contractible subgraphs C with their associated set
of edges
consists of corrupted edges with one endpoint in C i .
In the second stage we nd the MSF F i of each C i , and the MSF F 0 of the contracted
graph Gn(
3.1, the MSF of the whole graph is contained within
Note that at this point we have not identied any edges as being in the
MSF of the original graph G.
In the third stage we nd some MSF edges, via Boruvka steps, and recurse on the graph
derived by contracting these edges.
We execute the rst stage using the Partition procedure described in the previous section.
We execute the second stage with optimal decision trees. Essentially, these are hardwired
algorithms designed to compute the MSF of a graph using an optimal number of edge-weight
comparisons. In general, decision trees are much larger than the size of the problem that they solve
and nding optimal ones is very time consuming. We can aord the cost of building decision trees
by guaranteeing that each one is extremely small. At the same time, we make each conglomerate
formed by the C i to be su-ciently large so that the MSF F 0 of the contracted graph can be found
in linear time using the DenseCase algorithm.
Finally, in the third stage, we have a reduction in vertices due to the Boruvka steps, and a
reduction in edges due to the application of Lemma 3.1. In our optimal algorithm both vertices
and edges reduce by a constant factor, thus resulting in the recursive applications of the algorithm
on graphs with geometrically decreasing sizes.
4.1 Decision Trees
An MSF decision tree is a rooted tree having an edge-weight comparison associated with each
internal node (e.g. weight(x; y) < weight(w; z)). Each internal node has exactly two children, one
representing that the comparison is true, the other that it is false. The leaves of the tree list
the edges in some spanning tree. An MSF decision tree is said to be correct if the edge-weight
comparisons encountered on any path from the root to a leaf uniquely identify the spanning tree
at that leaf as the MSF. A decision tree is said to be optimal if it is correct and there exists no
correct decision tree with lesser depth.
Let us bound the time needed to nd all optimal decision trees for graphs of  r vertices by
brute force search. There are fewer than 2 r 2
such graphs and for each graph we must check all
possible decision trees bounded by a depth of r 2 . There are < r 4 possibilities for each internal node
and < r 2 r 2 +O(1)
decision trees to check. To determine if a decision tree is correct we generate all
possible permutations of the edge weights and for each, solve the MSF problem on the given graph.
Now we simultaneously check all permutations against a decision tree. First put all permutations
at the root, then move them to the left or right child depending on the truth or falsity of the
edge-weight comparison w.r.t to each permutation. Repeat this step until all permutations reach
a leaf. If for each leaf, all permutations sharing that leaf agree on the MSF, then the decision tree
is correct. This process takes no longer than (r for each decision tree. Setting
allows us to precompute all optimal decision trees in o(n) time.
Observe that in the high-level algorithm we gave in section 4, if the maximum size of each
component C i is su-ciently small, the components can be organized into a relatively small number
of groups of isomorphic components (ignoring edge weights). For each group we use a single
precomputed optimal decision tree to determine the MSF of components in that group.
In our optimal algorithm we will use a procedure DecisionTree(G; F), which takes as input a
collection of graphs G, each with at most r vertices, and returns their minimum spanning forests
in F using the precomputed decision trees.
5 The Algorithm
As discussed above, the optimal MSF algorithm is as follows. First, precompute the optimal
decision trees for all graphs with  log (3) n vertices. Next, divide the input graph into subgraphs
discarding the set of corrupted edges MC i as each C i is completed. Use the decision
trees found earlier to compute the MSF F i of each C i , then contract each connected component
spanned by F (i.e., each conglomerate) into a single vertex. The resulting graph has
n= log (3) n vertices since each conglomerate has at least log (3) n vertices by Lemma 3.2. Hence
we can use the DenseCase algorithm to compute its MSF F 0 in time linear in m. At this point,
by Lemma 3.1 the MSF is now contained in the edge set F . On this
graph we apply two Boruvka steps, reducing the number of vertices by a factor of four, and then
compute recursively. The algorithm is given below.
(this is used by the Soft Heap in the Partition procedure).
Precompute optimal decision trees for all graphs with  log (3) n 0 vertices, where n 0 is the number
of vertices in the original input graph.
If
r := log (3) jV (G)j
Partition(G;
G a :=
Apart from recursive calls and using the decision trees, the computation performed by Opti-
malMSF is clearly linear since Partition takes O(m log( 1
owing to the reduction in
vertices, the call to DenseCase also takes linear time. For
8 , the number of edges passed to the
nal recursive call is  m=4 giving a geometric reduction in the number of edges.
Since no MSF algorithm can do better than linear time, the bottleneck, if any, must lie in using
the decision trees, which are optimal by construction.
More concretely, let T (m; n) be the running time of OptimalMSF. Let T  (m; n) be the optimal
number of comparisons needed on any graph with n vertices and m edges and let T  (G) be the
optimal number of comparisons needed on a specic graph G. The recurrence relation for T is given
below. For the base case note that the graphs in the recursive calls will be connected if the input
graph is connected. Hence the base case graph has no edges and one vertex, and we have T (0; 1)
equal to a constant.
It is straightforward to see that if T  (m; n) = O(m) then the above recurrence gives T (m;
O(m). One can also show that T (m; n) = O(T  (m; n)) for many natural functions for T  (including
n)). However, to show that this result holds no matter what the function describing
T  (m; n) is, we need to establish some results on the decision tree complexity of the MSF problem,
which we do in the next section.
5.1 Some Results for MSF Decision Trees
In this section we establish some results on MSF decision trees that allow us to establish our main
result that OptimalMSF runs in O(T  (m; n)) time.
Proposition 5.1 T  (m; n)  m=2.
Proposition 5.2 For xed m and
Proposition 5.1 is obviously true since every edge should participate in a comparison to determine
inclusion in or exclusion from the MSF. Proposition 5.2 holds since we can add isolated vertices
to a graph, which obviously does not aect the MSF or the number of necessary comparisons.
We now state a property that is used by Lemmas 5.4 and 5.5.
Property 5.3 The structure of G dictates that
are edge-disjoint subgraphs of G.
are the components returned by Partition, it can be seen that the graph
Denition 5.3 since every simple cycle in this graph must be contained in exactly one of
the C i . To see this, consider any simple cycle and let i be the largest index such that C i contains
an edge in the cycle. Since each C i shares no more than one vertex with
contain an an edge from
. The proof of the following lemma can be found in [PR99b].
Lemma 5.4 If Property 5.3 holds for G, then there exists an optimal MSF decision tree for G
which makes no comparisons of the form e < f where e 2 C
Proof: Consider a subset P of the permutations of all edge weights where for e 2 C
holds that weight(e) < weight(f ). Permutations in P have two useful properties which
can be readily veried. First, any number of inter-component comparisons shed no light on the
relative weights of edges in the same component. Second, any spanning forest of a component is
the MSF of that component for some permutation in P.
Now consider any optimal decision tree T for G. Let T 0 be the subtree of T which contains only
leaves that can be reached by some permutation in P. Each inter-component comparison node in
must have only one child, and by the rst property, the MSF at each leaf was deduced using
only intra-component comparisons. By the second property, T 0 must determine the MSF of each
component correctly, and thus by Property 5.3 it must determine the MSF of the graph G correctly.
Hence we can contract T 0 into a correct decision tree T 00 by replacing each one-child node with its
only child. 2
Lemma 5.5 If Property 5.3 holds for G, then T
Proof: Given optimal decision trees T i for the C i we can construct a decision tree for G by replacing
each leaf of T 1 by T 2 , and in general replacing each leaf of T i by T i+1 and by labeling each leaf of
the last tree by the union of the labels of the original trees along this path. Clearly the height of
this tree is the sum of the heights of the T i , and hence T  (G)
need only prove
that no optimal decision tree for G has height less than the sum of the heights of the T i .
Let T be an optimal decision tree for G that has no inter-component comparisons (as guaranteed
by Lemma 5.4). We show that T can be transformed into a 'canonical' decision tree T 0 for G of
the same height as T , such that in T 0 , all comparisons for C i precede all comparisons for C i+1 , for
each i, and further, for each i, the subgraph of T 0 containing the comparisons within C i consists
of a collection of isomorphic trees. This establishes the desired result since T 0 must contain a path
that is the concatenation of the longest path in an optimal decision tree for each of the C i .
We rst prove this result for the case when there are only two components, C 1 and C 2 . Assume
inductively that the subtrees rooted at all vertices at a certain depth d in T have been transformed
to the desired structure of having the C 1 comparisons occur before he C 2 comparisons, and with all
subtrees for C 2 within each of the subtrees rooted at depth d being isomorphic. (This is trivially
the case when d is equal to the height of T .)
Consider any node v at depth d 1. If the comparison at that node is a C 1 comparison, then
all C 2 subtrees at descendent nodes must compute the same set of leaves for C 2 . Hence the subtree
rooted at v can be converted to the desired format simply by replacing all C 2 subtrees by one having
minimum depth (note that there are only two dierent C 2 subtrees { all C 2 subtrees descendent
to the left (right) child of v must be isomorphic). If the comparison at v is a C 2 comparison, we
know that the C 1 subtrees rooted at its left child x and its right child y must both compute the
same set of leaves for C 1 . Hence we pick the C 1 subtree of smaller height (w.l.o.g. let its root be
x) and replace v by x, together with the C 1 subtree rooted at x. We then copy the comparison at
node v to each leaf position of this C 1 subtree. For each such copy, we place one of the isomorphic
copies of the C 2 subtree that is a descendant of x as its left subtree, and the C 2 subtree that is a
descendant of y as its right subtree. The subtree rooted at x, which is now at depth d 1 is now
in the desired form, it computes the same result as in T , and there was no increase in the height of
the tree. Hence by induction T can be converted into canonical decision tree of no greater height.
Assume inductively that the result hold for up to k 1  2 components. The result easily
extends to k components by noting that we can group the rst k 1 components as C 0
1 and let C k
be C 0
. By the above method we can transform T to a canonical tree in which the C k comparisons
appear as leaf subtrees. We now strip the C k subtrees from this canonical tree and then by the
inductive assumption we can perform the transformation for remaining k 1 components. 2
Corollary 5.6 Let the C i be the components formed by the Partition routine applied to graph G,
and let G have m edges and n vertices. Then,
Corollary 5.7 For any m and n,
We can now solve the recurrence relation for the running time of OptimalMSF given in the
previous section.
(Corollary 5.6)
(Corollary 5.7 and Propositions 5.1, 5.2)
c  T  (m; n) (for su-ciently large c; this completes the induction)
This gives us the desired theorem.
Theorem 5.8 Let T  (m; n) be the decision-tree complexity of the MSF problem on graphs with
m edges and n nodes. Algorithm OptimalMSF computes the MSF of a graph with m edges and n
vertices deterministically in O(T  (m; n)) time.
6 Avoiding Pointer Arithmetic
We have not precisely specied what is required of the underlying machine model. Upon examina-
tion, the algorithm does not seem to require the full power of a random access machine (RAM). No
bit manipulation is used and arithmetic can be limited to just the increment operation. However, if
procedure DecisionTree is implemented in the obvious manner it will require using a table lookup,
and thus random access to memory. In this section we describe an alternate method of handling the
decision trees which can run on a pointer machine [Tar79], a model which does not allow random
access to memory. Our method is similar to that described in [B+98], but we ensure that the time
overhead in performing the table lookups during a call to DecisionTree is linear in the size of the
current input to DecisionTree.
A pointer machine distinguishes pointers from all other data types. The only operations allowed
on pointers are assignment, comparison for equality and dereferencing. Memory is organized into
records, each of which holds some constant number of pointers and normal data words (integers,
oats, etc. Given a pointer to a particular record, we can refer to any pointer or data word in that
record in constant time. On non-pointer data, the usual array of logical, arithmetic, and binary
comparison operations are allowed.
We rst describe the representation of a decision tree. Each decision tree has associated with it a
generic graph with no edge weights. This decision tree will determine the MST of each permutation
of edge weights for this generic graph. At each internal node of the decision tree are four pointers,
the rst two point to edges in the generic graph being compared and the second two point to the
left and right child of the node. Each leaf lists the edges in some spanning tree of the generic graph.
Since a decision tree is a pointer-based structure, we can construct each precomputed decision tree
(by enumerating and checking all possibilities) without using table lookups.
We now describe our representation of the generic graphs. The vertices of a generic graph are
numbered in order by integers starting with 1, and the representation consists of a listing of the
vertices in order, starting from 1, followed by the adjacency list for each vertex, starting with vertex
1. Each generic graph will have a pointer to the root of its decision tree.
Recall that we precomputed decision trees for all generic graphs with at most log (3) n 0 vertices
(where n 0 is the number of vertices in the input graph whose MSF we need to nd). The generic
graphs will be generated and stored in lexicographically sorted order. Note that with our represen-
tation, in the sorted order the generic graphs will appear in nondecreasing order of the number of
vertices in the graph.
Before using a decision tree on an actual graph (which must be isomorphic to the generic graph
for that decision tree), we must associate each edge in the actual graph with its counterpart in the
generic graph. Thus a comparison between edge weights in the generic graph can be substituted
by the corresponding weights in the actual graph in constant time.
On a random access machine, we can encode each possible graph in a single machine word (say,
as an adjacency matrix), then index the generic graph in an array according to this representation.
Thus given a graph we can nd the associated decision tree in constant time. On a pointer machine
however, converting a bit vector or an integer to a pointer is specically disallowed.
We now describe our method to identify the generic graph for each C i e-ciently. We assume
that each C i is specied by the adjacency lists representation, and that each edge (x; y) has a pointer
to the occurrence of (y; x) in y's adjacency list. Each edge also has a pointer to a record containing
its weight. Let m and n be the number of edges and vertices in
We rewrite each C i in the same form as the generic graphs, which we will call the numerical
representation. Let C i have p vertices (note that p  r). We assign the vertices numbers from 1 to
p in the order in which they are listed in the adjacency lists representation, and we rewrite each
edge as a pair of such numbers indicating its endpoints. Each edge will retain the pointer to its
weight, but that is separate from its numerical representation.
We then change the format for each graph as follows: Instead of a list of numbers, each in the
range [1::r], we will represent the graph as a list of pointers. For this we initialize a linked list with
r buckets, labeled 1 through r. If, in the numerical representation the number j appears, it will be
replaced by a pointer to the j th bucket.
We transform a graph into this pointer representation by traversing rst the list of vertices and
then the list of edges in order, and traversing the list of buckets simultaneously, replacing each
vertex entry, and the rst vertex entry for each edge by a pointer to the corresponding bucket.
Thus edge (x; y), also appearing as (y; x), will now appear as (ptr(x); y) and (ptr(y); x). We then
employ the twin pointers to replace the remaining y and x with their equivalent pointers. Clearly
this transformation can be performed in O(m) time, where m is the sum of the sizes of all of the
We will now perform a lexicographic sort [AHU74] on the sequence of C i 's in order to group
together isomorphic components. With our representation we can replace each bucket indexing
performed by traditional lexicographic sort by an access to the bucket pointer that we have placed
for each element. Hence the running time for the pointer-based lexicographic sort is O(
is the length of the i th vector and DecisionTree is called
with graphs of size r = O(log (3) n), we have and the sum of the sizes of the graphs is
O(m). Hence the radix sort can be performed in O(m
Finally, we march through the sorted list of the C i 's and the sorted list of generic graphs,
matching them up as appropriate. We will only need to traverse an initial sequence of the sorted
generic graphs containing O(2 r 2
entries in order to match up the graphs. This takes time O(m
7 Performance on Random Graphs
Even if we assume that MST has some super-linear complexity, we show below that our algorithm
runs in linear time for nearly all graphs, regardless of edge weights. This improves upon the
expected linear-time result of Karp and Tarjan [KT80], which depended on the edge weights being
chosen randomly. Our result may also be contrasted with the randomized algorithm of Karger et al.
[KKT95], which is shown to run in O(m) time w.h.p. by a proof that depends on the permutation of
edge weights and random bits chosen, not the graph topology. In fact, none of the earlier published
MST algorithms appear to have this property of running in linear time w.h.p. on random graphs
for all edge-weights. Using the analysis of this section and suitably souped-up versions of earlier
algorithms [FT87, GGST86, Chaz00], we may obtain the same high probability result.
Our analysis hinges on the observation that for sparse random graphs, w.h.p. any subgraph
constructed by the Partition routine has only a miniscule number in edges in excess of the number
of spanning forst edges in that subgraph. The MST of such graphs can be computed in linear time,
and hence the computation on optimal decision trees takes linear time on these graphs.
Throughout this section  will denote (m; n).
Theorem 7.1 The MST of a graph can be found in linear time with probability
e
graph drawn from G n;m
graph drawn from G n;p .
Both (1) and (2) hold regardless of the permutation of edge weights.
In the next section we describe the edge-addition martingale for the G n;m model. In section 7.2
we use this martingale and Azuma's inequality to prove part (1) of Theorem 7.1. Part (2) is shown
to follow from part (1).
7.1 The Edge-Addition Martingale
Consider the G n;m random graph model in which each graph with n labeled vertices and m edges
is equally likely. For analytical purposes, we select a random graph by beginning with n vertices
and adding one edge at a time [ER61]. Let X i be a random edge s.t. X i
be the graph made up of the rst i edges, with G 0 being the graph on n vertices
having no edges.
A martingale is a sequence of random variables Y
We now prove that if g is any graph-theoretic function and
for is a martingale.
Lemma 7.2 The sequence m, is a martingale, where g is any
graph theoretic function, G 0 is the edge-free graph on n vertices, and G i is derived from G i 1 by
adding a random edge not in G i 1 to G i 1 .
g. Given that G i 1 has been xed,
call the sequence proved to be a martingale in Lemma 7.2 the edge-addition martingale in
contrast to the edge-exposure martingale for G n;p .
We now recall the well-known Azuma's inequality (see, e.g., [AS92]).
Theorem 7.3 (Azuma'a Inequality.) Let Y Ym be a martingale with jY
m. Let  > 0 be arbitrary. Then Pr[jY
To facilitate the application of Azuma's inequality to our edge-addition martingale we establish
the following lemma.
Lemma 7.4 Consider the sequence proved to be a martingale in Lemma 7.2. Let g be any graph-theoretic
function such that jg(G) g(G 0 )j  1 for any pair of graphs G and G 0 of the form
are the average of
range over their possible outcomes, given G i and G i 1 respectively. We identify each outcome
of
with equal-size disjoint sets of outcomes of X m
which cover all outcomes of X m
. Then
may be regarded as an average of set averages. If, for each set corresponding to an
outcome P of X m
we establish that the set average diers from g(G i [ P ) by no more than 1,
the Lemma follows.
The correspondence is as follows. Let a. For each outcome x m
, the corresponding set
consists of outcomes x j
ranges over all edges not
appearing in G i 1 and x m
. For each outcome
i+1 and all Q in P 's associated set,
since the graphs dier in at most one edge. Clearly
holds as well, where the average is over outcomes Q in P 's associated
set. 2
7.2 Analysis
We dene the excess of a subgraph H to be jE(H)j jF (H)j, where F (H) is any spanning forest
of H. Let f(G) be the maximum excess of the graph made up of intra-component edges, where the
sets of components range over all possible sets returned by the Partition procedure. (Recall that the
size of any component is no more than
The key observation leading to our linear-time result is that each pass of our optimal algorithm
denitely runs in linear time if f(G)  m=(m;n). To see this, note that if this bound on f(G)
holds, we can reduce the total number of intra-component edges to  2m= in linear time using
log  Boruvka steps, and then, clearly, the MST of the resulting graph can be determined in O(m)
time. We show below that if a graph is randomly chosen from G n;m , f(G)  m=(m;n) with high
probability.
We now show that Lemma 7.4 applies to the graph-theoretic function f , and then apply Azuma's
inequality to obtain our desired result.
Lemma 7.5 Let be two graphs on a set of labeled vertices which
dier by no more than one edge. Then jf(G) f(G 0 )j  1.
Proof: Suppose w.l.o.g. that f(G) f(G 0 ) > 1, then we could apply the optimal set of components
of G to G 0 . Every intra-component edge of G remains an intra-component edge, except possibly
e. This can reduce the excess by no more than one, a contradiction. The possibility that e 0 may
become an intra-component edge can only help the argument. 2
Lemma
Proof: Notice that if m
simply impossible to have m= intra-component edges, so we
assume m
An upper bound on f E (G 0 ) is the expected number of indices i s.t. edge X i completed a cycle
of length  k in G i 1 , since all edges which caused f to increase must have satised this criterion.
be the probability that X i completed a cycle of length  k. By bounding the number of
such cycles, and the probability they exist in the graph, we have
Y
<n

nm
(recall that i  m)
O

n)

In either case, f
G be chosen from G n;m . Then Pr[f(G) > m=] < e
Proof: By applying Azuma's inequality, we have that Pr[jf E (Gm
Setting
m gives the Lemma. Note that by Lemma 7.6 f
insignicant. 2
We are now ready to prove Theorem 7.1.
Proof: We examine only the rst log k passes of our optimal algorithm, since all remaining passes
certainly take o(m) time. Lemma 7.7 assures us that the rst pass runs in linear time w.h.p.
However, the topology of the graph examined in later passes does depend on the edge weights.
Assuming the Boruvka steps contract all parts of the graph at a constant rate, which can easily
be enforced, a partition of the graph in one pass of the algorithm corresponds to a partition of the
original graph into components of size less than k c , for some xed c. Using k c in place of k does
not aect Lemma 7.6, which gives the Theorem for G n;m , that is, part (1). For G n;p note that the
probability that there are not (pn 2 ) edges is exponential in pn 2 ), hence the probability that
the algorithm fails to run in linear time is dominated by the bound in part (1).For the sparse case where m < n=, Theorem 7.1 part (1) holds with probability 1, and for
< 1=n, by a Cherno bound, part (2) holds with probability 1 e
n=) .
An intriguing aspect of our algorithm is that we do not know its precise deterministic running
time although we can prove that it is within a constant factor of optimal. Results of this nature
have been obtained in the past for sensitivity analysis of minimum spanning trees [DRT92] and
convex matrix searching [Lar90]. Also, for the problem of triangulating a convex polygon, it
was observed in [DRT92] that an alternate linear-time algorithm could be obtained using optimal
decision trees on small subproblems. However, these earlier algorithms make use of decision trees
in more straightforward ways than the algorithm presented here.
As noted in Section 4.1, the construction of optimal decision trees takes sub-linear time. Thus, it
is important to observe that our use of decision trees does not result in a large constant factor in the
running time. Further, this construction of optimal decision trees is performed by a straightforward
brute-force search, hence the resulting algorithm is uniform.
It was mentioned in the introduction that an optimal algorithm can be constructed for any prob-
lem, given an optimal verication algorithm for that problem [Jo97]. This construction produces an
algorithm which enumerates programs (for some machine model) and executes them incrementally.
Whenever one of the programs halts the verier checks its output for correctness. Using a linear-time
MST verication algorithm such as [DRT92, K97, B+98], this construction yields an optimal
MST algorithm, however it is unsatisfactory for several reasons. Aside from truly astronomical
constant factors (roughly exponential in the size of the optimal program), the algorithm is optimal
only with respect to a particular machine model (say a TM, a RAM, or a pointer machine). Our
result, in contrast, is robust in that it ties the algorithmic complexity of MST to its decision-tree
complexity, a limiting factor in any machine model. It is not always the case that algorithmic complexity
and decision-tree complexity are asymptotically equivalent. In fact, one can easily concoct
simple problems which are NP-hard but nevertheless have polynomial-depth decision-trees (e.g. nd
the lightest edge on any Hamiltonian path). See [GKS93], [PR01, Section 8] for two sorting-type
problems whose decision-tree complexity and algorithmic complexity provably diverge.
9 Conclusion
We have presented a deterministic MSF algorithm that is provably optimal. The algorithm runs
on a pointer machine, and on graphs with n vertices and m edges, its running time is O(T  (m; n)),
where T  (m; n) is the decision-tree complexity of the MSF problem on n-node, m-edge graphs.
Also, on random graphs our algorithm runs in linear time with high probability for all possible
edge-weights. Although the exact running time of our algorithm is not known, we have shown that
the time bound depends only on the number of edge-weight comparisons needed to determine the
MSF, and not on any data structural issues.
Determining the worst-case complexity of our algorithm is the main open question remaining
in the MSF problem, however, there is a subtler open question. We have given an optimal uniform
algorithm for the MSF problem. Is there an optimal uniform algorithm which does not use
precomputed decision trees (or some similar technique)? More generally, are there problems where
precomputation is necessary? One may wish to study this issue in a simpler setting, say the MSF
verication problem on a pointer machine. Here there is still an (m; n) factor separating the best
pointer machine algorithm which uses precomputed decision trees [B+98] and the one which does
not [Tar79b].
One may also ask for the parallel complexity of the MSF problem. Here, resolved recently
were the randomized work-time complexity [PR99] and the deterministic time complexity [CHL99]
of the MSF problem on the EREW PRAM. An open question that remains here is to obtain a
deterministic work-time optimal parallel MSF algorithm. Parallelizing our optimal algorithm is
not at all straightforward. Although handling decision trees does not present any problems in the
parallel context, we still need a method for identifying contractible components in parallel and a
base case algorithm that performs linear work for graph-densities of log (3) n. Existing sequential
algorithms which are suitable for the base case, such as the one in [FT87], are also not easily
parallelizable.



--R

The Design and Analysis of Computer Algorithms.
The Probabilistic Method.


A faster deterministic algorithm for minimum spanning trees.

A minimum spanning tree algorithm with inverse-Ackermann type complexity
On the parallel time complexity of undirected connectivity and minimum spanning trees.
A note on two problems in connexion with graphs.


Fibonacci heaps and their uses in improved network optimization algorithms.


On the history of the minimum spanning tree problem.
Optimal randomized algorithms for local sorting and set- maxima

Computability and Complexity: From a Programming Perspective.
A randomized linear-time algorithm to nd minimum spanning trees
Linear expected-time algorithms for connectivity problems
A simpler minimum spanning tree veri
An optimal algorithm with unknown time complexity for convex matrix searching.
A randomized time-work optimal parallel algorithm for nding a minimum spanning forest <Proceedings>Proc
An optimal minimum spanning tree algorithm.
Computing undirected shortest paths with comparisons and additions.
Finding minimum spanning trees in O(m
Shortest connection networks and some generalizations.
A class of algorithms which require nonlinear time to maintain disjoint sets.
Applications of path compression on balanced trees.
--TR
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
Fibonacci heaps and their uses in improved network optimization algorithms
An optimal algorithm with unknown time complexity for convex matrix searching
Verification and sensitivity analysis of minimum spanning trees in linear time
Optimal randomized algorithms for local sorting and set-maxima
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
A randomized linear-time algorithm to find minimum spanning trees
Computability and complexity
Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators
Applications of Path Compression on Balanced Trees
The soft heap
A minimum spanning tree algorithm with inverse-Ackermann type complexity
Concurrent threads and optimal parallel minimum spanning trees algorithm
Computing shortest paths with comparisons and additions
Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms
The Design and Analysis of Computer Algorithms
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
A Faster Deterministic Algorithm for Minimum Spanning Trees
Finding Minimum Spanning Trees in O(m alpha(m,n)) Time

--CTR
Jess Cerquides , Ramon Lpez Mntaras, TAN Classifiers Based on Decomposable Distributions, Machine Learning, v.59 n.3, p.323-354, June      2005
Artur Czumaj , Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear-time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Tzu-Chiang Chiang , Chien-Hung Liu , Yueh-Min Huang, A near-optimal multicast scheme for mobile ad hoc networks using a hybrid genetic algorithm, Expert Systems with Applications: An International Journal, v.33 n.3, p.734-742, October, 2007
Seth Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoretical Computer Science, v.312 n.1, p.47-74, 26 January 2004
Ran Mendelson , Robert E. Tarjan , Mikkel Thorup , Uri Zwick, Melding priority queues, ACM Transactions on Algorithms (TALG), v.2 n.4, p.535-556, October 2006
Amos Korman , Shay Kutten, Distributed verification of minimum spanning trees, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
optimal complexity;graph algorithms;minimum spanning tree