# Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2

I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm

As described in the wiki article, it works in 5 steps to find the MSF for a graph $$G = (V, E)$$:

1. Do two iterations of Boruvka resulting in a graph $$G'= (V', E')$$
2. Select each edge from $$E'$$ with probability $$1/2$$ and get set of selected edges $$E''$$
3. Call yourself recursively on the graph $$G'' = (V', E'')$$ and get an MST $$F = (V', E''')$$
4. Find the set $$L$$ of all F-light edges
5. Call yourself recursively on the graph $$G''' = (V', E''' \cup L)$$

I understand the correctness and the expected performance for this. However, if I change the probability in step 2 from 1/2 to some other probability $$p$$, the time analysis breaks down for me and I can no longer prove that it will work in expected linear time. How do I reason about $$p$$? Does $$p$$ need to be exactly 1/2 for the algo to work in linear time? Why?

## 1 Answer

Here is performance analysis adapted slightly from section $$\S7.14$$ of State-of-the-Art Algorithms for Minimum Spanning Trees by Jason Eisner, (1997). It corrects some very mild mistakes in that Wikipedia article as well as in the original paper (1995) by the inventors of the algorithm.

Let $$\langle m, n\rangle$$ denote a call of the algorithm on a graph (not necessarily connected) with $$n$$ nodes and $$m$$ edges. The initial call is $$\langle m_0, n_0\rangle$$.

A call $$\langle m, n\rangle$$ takes time $$O(m+n)$$, exclusive of the recursive calls at step 3 and step 5. So the total running time is proportional to the total number of edges plus the total number of vertices over all calls.

Let we consider the binary tree of recursive calls: each call $$\langle m, n\rangle$$ (with $$n\gt1$$) spawns both a left-child call, which is the step 3 and a right-child call, which is the step 5.

These child calls have at most $$n/4$$ vertices apiece, thanks to the two Borůvka passes at step 1. So the call tree has $$O(n_0)$$ vertices total.

Now consider the total number of edges in the call tree.

The call $$\langle m, n\rangle$$ has a left child of expected size $$\langle m/2, n/4\rangle$$ or smaller, and a right child of expected size $$\langle n/2, n/4\rangle$$ or smaller. We have two observations.

• At depth $$d$$ in the tree, there are $$2^{d−1}$$ right children of expected size at most $$\langle 2n_0/4^d, n_0/4^d\rangle.$$
• The call $$\langle m, n\rangle$$ together with all its left-spine descendants has at most $$m + m/2 + m/4 + \cdots= 2m$$ expected edges.

Every call is a left-spine descendant of the root or of a right child.

• The root and its left spine descendants expect at most $$2m_0$$ total edges.
• A right child at depth $$d$$ and its left-spine descendants expect at most $$2 · 2n_0/4^d=n_0/4^{d-1}$$ total edges.

Summing these bounds over the root and all right children, we obtain a bound on expected edges of $$2m_0 +\sum^\infty_{d=1}2^{d-1}n_0/4^{d-1}=2m_0 + 2n_0$$. So the expected tims is $$O(m_0)$$.

#### What happens if we change probablity from $$1/2$$ to $$p$$?

What we need to reconsider is the total number of edges in the call tree.

The call $$\langle m, n\rangle$$ has a left child of expected size $$\langle mp, \frac n4\rangle$$ or smaller, and a right child of expected size $$\langle \frac n{4p}, \frac n4\rangle$$ or smaller. We have two observations.

• At depth $$d$$ in the tree, there are $$2^{d−1}$$ right children of expected size at most $$\langle \frac {n_0}{4^dp}, \frac{n_0}{4^d}\rangle.$$
• The call $$\langle m, n\rangle$$ together with all its left-spine descendants has at most $$m + mp + mp^2 + \cdots= \frac m{1-p}$$ expected edges.

Every call is a left-spine descendant of the root or of a right child.

• The root and its left spine descendants expect at most $$\frac {m_0}{1-p}$$ total edges.
• A right child at depth $$d$$ and its left-spine descendants expect at most $$\frac{\frac{n_0}{4^dp}}{(1-p)}$$ total edges.

Summing these bounds over the root and all right children, we obtain a bound on expected edges of $$\frac{m_0}{1-p} +\sum^\infty_{d=1}2^{d-1}\frac{\frac{n_0}{4^{d}p}}{(1-p)}=\frac{m_0}{1-p} + \frac{n_0}{2p(1-p)}.$$ So the expected tims is still $$O(m_0)$$.