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.

• Not just numerically representative but structurally

Intuition: “fences” like selection algorithm.

sampling theorem:

• $F$-Light edges
  • Edge that is "better" than edge in $F$
  • Not connected by a path of lighter edges in $F$
• 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:

• first 3 Boruvka steps to $n/8$ vertices
• then sample, verify, clean up
• $O(m+n)$ work at top level
• sample problem has $m/2$ edges and $n/4$ vertices
• cleanup problem has $n/8$ vertices so $n/4$ edges.
• total size of the subproblems is $m/2+n/4+n/8+n/4=(m+n)/2$
• ie, linear work cuts problem size in half
• so, linear work overall
• (total size of all problems is $2(m+n)$).

$$ \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.