Editing Minimum spanning tree (section)

=== Optimal algorithm ===

[[Seth Pettie]] and [[Vijaya Ramachandran]] have found a {{not a typo|provably}} optimal deterministic comparison-based minimum spanning tree algorithm.<ref name=PettieRamachandran2002>{{citation
 | last1 = Pettie | first1 = Seth
 | last2 = Ramachandran | first2 = Vijaya
 | doi = 10.1145/505241.505243
 | mr = 2148431
 | issue = 1
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 16–34
 | title = An optimal minimum spanning tree algorithm
 | url = https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf
 | volume = 49
 | year = 2002| s2cid = 5362916
 }}.</ref> The following is a simplified description of the algorithm.

# Let {{math|1=''r'' = log log log ''n''}}, where {{mvar|n}} is the number of vertices. Find all optimal decision trees on {{mvar|r}} vertices. This can be done in time {{math|''O''(''n'')}} (see [[#Decision trees|Decision trees]] above).
# Partition the graph to components with at most {{mvar|r}} vertices in each component. This partition uses a [[soft heap]], which "corrupts" a small number of the edges of the graph.
# Use the optimal decision trees to find an MST for the uncorrupted subgraph within each component.
# Contract each connected component spanned by the MSTs to a single vertex, and apply any algorithm which works on [[#Dense graphs|dense graphs]] in time {{math|''O''(''m'')}} to the contraction of the uncorrupted subgraph
# Add back the corrupted edges to the resulting forest to form a subgraph guaranteed to contain the minimum spanning tree, and smaller by a constant factor than the starting graph. Apply the optimal algorithm recursively to this graph.

The runtime of all steps in the algorithm is {{math|''O''(''m'')}}, ''except for the step of using the decision trees''. The runtime of this step is unknown, but it has been proved that it is optimal - no algorithm can do better than the optimal decision tree. Thus, this algorithm has the peculiar property that it is ''{{not a typo|provably}} optimal'' although its runtime complexity is ''unknown''.