Deterministic Linear-Time Minimum Spanning Tree Problem

Deterministic Linear-Time Minimum Spanning Tree Problem

Definitions and mathematical statement

An instance is a connected graph with $n$ vertices, $m$ edges, and distinct real edge weights. A minimum spanning tree is a connected acyclic spanning edge set minimizing the sum of its edge weights. Seek one uniform deterministic algorithm that finds it in worst-case $O(m)$ time in the comparison-based pointer-machine model of Pettie--Ramachandran.

Weights are available through comparisons, not through unrestricted numerical operations or integer addressing. A pointer machine manipulates records and pointers using the operations permitted in that model. The linear bound is required on every input, not only in expectation or for a special distribution. A linear comparison count without a matching implementation time bound would not by itself meet this target.

Formulation and concept references: [S1].

Short English statement

Can minimum spanning trees always be found deterministically in linear time when arbitrary real weights may only be compared?

Research attempt

Scope and first unresolved step.

This attempt by GPT-6 Astra Ultra, prepared on 27 September 2026, reconstructs the safe-edge argument, implements it on cactus graphs, and audits the cost of repeated contraction. It treats weights as comparison-only real values. Arithmetic on weight representations and integer sorting are not available. The partial algorithms below are standard, and no new general linear algorithm is claimed.

Pettie--Ramachandran [S1] obtain a pointer-machine algorithm whose running time matches the optimal comparison-tree complexity, while explaining that the exact asymptotic value of that complexity is not known. Optimality in that sense is not an asserted $O(m)$ bound. The first remaining step in this attempt is a general filtering or contraction argument whose total pointer operations and comparisons, over all phases, are $O(m)$ on every input.

The one-vertex case is handled directly in constant time. Self-loops, if present in the input convention, are discarded during a linear scan. The cactus subcase below is stated for simple connected graphs.

The cut rule, proved by exchange.

For a nonempty proper vertex set $A$, let $e$ be its lightest crossing edge. Distinct weights make $e$ unique. Suppose a minimum spanning tree $T$ omits $e$. Adding $e$ creates a cycle. Since its endpoints are on opposite sides of the cut, the $T$-path between them contains another crossing edge $f$. Its weight is greater than that of $e$, so deleting $f$ yields a spanning tree of smaller total weight, a contradiction. Thus $e$ belongs to every minimum spanning tree.

The dual cycle rule is equally precise: the heaviest edge $e$ of a cycle belongs to no minimum spanning tree. If a purported minimum tree contains it, deleting it splits that tree into two parts. The rest of the cycle has an edge $f$ crossing this cut, and $w(f)<w(e)$. Replacing $e$ by $f$ improves the tree.

These arguments use addition of weights only to compare mathematical objective values. The algorithmic decisions themselves require comparisons of individual weights. They are valid for negative as well as positive distinct weights.

A deterministic linear algorithm on cactus graphs.

A connected cactus has each edge in at most one simple cycle. Every edge outside its cycles is a bridge and must belong to a spanning tree. For each cycle, delete its unique heaviest edge and retain all other edges. The resulting graph is connected: the removed edge can be replaced along the rest of its cycle. It is acyclic because all the simple cycles have been broken, so it is a spanning tree.

It is minimum by the cycle rule, or by the following direct optimization. If there are $c$ cycles, the cactus has $m=n-1+c$ edges. A spanning tree omits $c$ edges and must omit at least one from each of the $c$ edge-disjoint cycles. Therefore it omits exactly one from each cycle and no bridge. Minimizing retained weight is equivalent to maximizing the omitted weight separately in each cycle, which is achieved by the rule.

A depth-first traversal identifies these cycles in $O(m+n)$ pointer operations. Store parent pointers and an edge stack in vertex/edge records. Each non-tree edge closes the path to an ancestor; in a cactus these cycle paths are edge-disjoint, so tracing and marking them charges each edge at most once. Comparing weights along a cycle identifies its maximum in time proportional to its length. Summing over the disjoint cycles and bridges gives $O(m+n)=O(m)$ for nontrivial connected instances.

This algorithm uses neither a sorted edge list nor disjoint-set operations with unbounded integer addressing. It meets the model and worst-case target for the stated subclass.

The general contraction baseline.

Maintain components of a forest already known to lie in the minimum spanning tree. During one phase, scan the edge records and select the lightest outgoing edge of each component. The cut rule makes each selected edge safe. The distinct selected edges form a forest: if they contained a cycle in the component graph, its heaviest edge could not be chosen by either endpoint component, since each endpoint has a lighter incident edge on that cycle.

Unless only one component remains, every component has an outgoing edge because the original graph is connected. Every connected component of the selected forest therefore contains at least two old components. Contracting selected edges at least halves their number. After at most $\lceil\log_2 n\rceil$ phases the selected edges span the graph.

A pointer-machine implementation can maintain a component-record pointer at each original vertex, scan all original edges, and traverse the selected forest to update components. This uses $O(m+n)$ time per phase and $O(m\log n)$ time in total. The argument is complete but misses the requested linear bound. Counting only the number of contractions, which is $n-1$, omits the repeated scans that find them.

A countertest to charging scans only to contractions.

The same naive phase implementation can repeatedly inspect edges that are never selected. Consider $2^h$ vertices grouped in a binary hierarchy. Within each bottom pair put a very light edge, and at each successive level provide heavier edges linking its two child groups, with perturbations making all weights distinct. Include many very heavy edges between the two top-level halves. Choose weight ranges so that, until the top level, each component's lightest outgoing edge links within its next hierarchical group.

The early contractions merge groups inside each half, while the heavy cross-half records remain outgoing and are rescanned. If the implementation scans the original list at every phase, these records are inspected for order $h$ phases. Their endpoints eventually become duplicate component pairs, but the naive implementation has not removed the duplicates. Thus an edge can incur logarithmically many inspections while contributing to no contraction.

This does not prove that all contraction algorithms require that cost. Removing redundant parallel edges or introducing stronger filtering may help, and the optimal algorithms do much more. It pinpoints why the stated accounting fails: the potential function must also pay for unsuccessful edge inspections, not just successful merges.

Why sorting is neither a solution nor a lower bound.

Sorting the real weights and applying a greedy scan gives a valid route to an MST, but comparison sorting generally costs $O(m\log m)$. That upper bound does not meet the question. Conversely, a sorting lower bound cannot simply be transferred to MST, because an MST output does not determine the sorted order.

For a tree-shaped input, every edge belongs to the answer, regardless of the ordering of its distinct weights. The topology alone solves the instance with no weight comparisons. On a single cycle, finding only the maximum suffices and takes linear comparisons, again without learning the whole order. Any genuine superlinear lower bound for the selected MST model would need an argument respecting the information actually demanded by the output.

A similar distinction applies to verification. A proposed tree can be characterized by the requirement that each non-tree edge be no lighter than the maximum edge on its tree path. Proving or testing that characterization does not automatically construct a suitable tree within the same budget: one must supply the candidate and account for the operations used to obtain it.

Verification and outcome.

Finite checks compare the cactus deletion rule against exhaustive spanning-tree enumeration on small weighted cactus examples, including a shared-vertex pair of cycles and negative weights. They separately check the cut and cycle rules on general small graphs. The operation bound is established by the edge-disjoint cycle traversal, rather than inferred from the speed of a Python test.

UNRESOLVED. A comparison-based deterministic linear algorithm is proved for cactus graphs, and the general safe-contraction baseline is audited at $O(m\log n)$. The missing theorem is a worst-case linear total-work bound for arbitrary connected graphs, including both comparisons and pointer operations.

Sources

• S1 Seth Pettie, Vijaya Ramachandran, "An Optimal Minimum Spanning Tree Algorithm," Journal of the ACM 49$1$:16-34, 2002. https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf. Formulation source.