MST

Review Background

• Prim
• Kruskal
• Boruvka
  • contract smallest edge incident on each vertex
  • creates connected components of contracted edges
  • each has at least 2 vertices
  • so at most $n/2$ components
• verification:
  • Komlos: $O(m)$ compares, but slow to figure out
  • Dixon: $O(m)$ time by brute-forcing small problems via Komlos

Idea: sample representative subproblem.

Intuition: “fences” like selection algorithm.

sampling theorem:

• $F$-Light edges
• pick $S=G(p)$, construct optimal $F$
• get $n/p$ $F$-light edges

Recursive algorithm without boruvka: \[ T(m,n) = T(m/2,n)+O(m) + T(2n,n) = O(m+n\log n) \] (being sloppy claiming expectation on T(2n,n))

Recursive algorithm with 3 boruvka steps: $$ \begin{align*} T(m,n) &= T(m/2,n/8) + c_1( m+n) + T(n/4,n/8)\\ &\le c(m/2+n/8) + c_1 (m+n) + c(n/4+n/8)\\ &=(c/2+c_1)m + (c/8+c_1+c/4+c/8)n\\ &= (c/2+c_1)(m+n) \end{align*} $$ so set $c=2c_1$ (not sloppy: expectation works thanks to linearity).

Can show holds with high probability.

Notes:

• Matroids
• Chazelle $m\log\alpha(m,n)$ via relaxed heap
• Ramachandran and Peti optimal deterministic algorithm (runtime unknown)
• open questions.