The Minimum Spanning Tree (MST) problem

Exercise: Show that the binomial tree B_k has 2^k nodes. Then argue that there are at most O(log n) trees. Binomial queue analysis:

• At first it seems we have the following:
  • Insert: O(log n) because of all the "carry" operations that might occur.
  • Extract-min: O(log n) because all the subtrees need to be added (a queue-merge operation).
  • Decrease-key: O(log n) as in binary heap.

• However, consider this:

  

  • When a carry ripples, it also leaves behind 0's.
          → Reduces the need for carries in the future.
          → Over time, the actual number of carries may not be high.

• We want to account for the average cost of an operation over time
        → Called amortized analysis.
  • This is still a worst-case (not average).
  • It's really a "worst possible average cost".

• The idea of a potential function:
  • In physics, "work done" results in storing potential energy.
  • The analog here: "work done" in carries stores "good" zeroes.

• Amortized analysis of insert-operation:
  • Let P_i = potential = number of 0's after i-th insert.
  • Let P_i - P_i-1 = change in potential.
  • Let C_i = true cost of i-th insert.
  • Then
          C_i = 1 + P_i - P_i-1
    i.e., cost = cost-of-new-item  +   ripple-carry
  • Hence, over n operations
          Σ >C_i = n + P_n - P₀
          ≤ 2n
  • Thus, average cost is
          (1/n) Σ C_i = O(1).

• Note:
  • Above we equated "potential" with "good" zeroes.
  • We could just as easily equate "potential" with "bad" ones.
          → Exactly the same analysis but with change-of-sign for potential.

• Unfortunately: for extract-min and decrease-key, the amortized time is still O(log n).

The Fibonacci heap [Fred1987]: an overview

• The fibonacci heap is a modification of the binomial such that
  • Decrease-key takes O(1) amortized.
  • Extract min takes O(log n) amortized.

• Again, we switch to calling it a fibonacci queue because whole thing is a collection of trees.

• The fib-queue is based on two ideas:
  1. When a decrease-key occurs, don't repair tree.
           → Instead, "cut out" the subtree where the decrease-key occurs.
  2. Dispense with the strict binomial-tree properties:
     • Dispense with: at most one B_k tree.
     • Dispense with: recursive structure of each B_k.

More detail:

• Define
        rank (node) = number of children of the node
        rank (tree) = rank (tree's root)

• Maintain a list of trees with min-pointer, as in binomial queue.

• When we merge trees, we will merge two trees of equal rank and create a one-rank-higher tree.

  

• Cascading cut:
  • When doing a decrease-key, if heap-order is violated, cut-out node along with subtree:

    

  • Then, "mark" the parent.
  • A parent with two marks is itself cut-out (as a single-node tree):

    

  • The cutting cascades upwards as long as marked parents need to be cut out.

• Lazy-merge:
  • When a cut tree is added to main list, simply concatenate
          → Do not perform a merge.
  • A merge is performed only during extract-min.

• Decrease-key operation:
  • As described above: cut out if needed and cascade backwards.
  • Note: O(1) time except for cascades.
          → Will turn out to be O(1) amortized.

• Extract-min operation:
  • Remove node as in binomial queue.
  • Perform a full merge:
    • Start by "adding" the single nodes and work towards adding higher-rank trees.
    • Algorithm:

      
                   for r = 0 to M
                       while # rank-r trees > 2
                           merge into a rank r+1 tree
                       endwhile
                   endfor
                   

    • Here, M = the largest rank possible (which is O(log n)).

Exercise: Look up Fibonacci numbers. How are they defined recursively? Prove the following:

• F₀ + ... F_n-2 = F_n - 1.
• F_k = O(φ^k), where φ is the golden ratio.

Analysis:

• First, observe:
  • If C_i is the i-th youngest child of a node N, then rank(C_i) ≥ 2
  • Proof:
    • When C_i is joined with N (during a merge), N had children C₁, C₂, ... C_i-1.
    • Nodes are joined only if they have the same rank.

      

    • After merging, it can lose children, but at most one
            → Else, it would itself be cut.
    • Thus, it has at least i-2 children.

• Next: a node of rank r has O(F_r) descendants (not just children).
  • Let T_r be the smallest tree (fewest nodes) of rank r.
  • Then size of T₀ = 1 (single node).

    

    
          → |T₀| = F₁ and |T₁| = F₂, the second two Fibonacci numbers.

  • Now consider a rank r tree and order children by age:

    

  • To make the smallest possible tree, assume all children are minimal subtrees.
          → |T_r| ≥ 1 + |T₀| + ... + |T_r-1| = O(F_r).
  • But F_r = O(φ^r).
  • Thus, r = O(log|T_r|).
  • Thus, with at most n nodes, the rank is at most O(log n).

• Define the "badness" potential as:
        potential = #trees + #marked-nodes

• For decrease-key:
  • Let C = length of cascade.
  • Then, actual cost = C.
  • We create O(C) new trees, but reduce marked nodes by O(C).
          → Total change in potential is O(1).
  • Amortized cost: O(1).

• For extract-min:
  • Does not change # of marked nodes.
  • Total # trees is like the total number of 1's in binary addition.
          → Same change in potential over a number of operations.
  • Total time is bounded by O(log n), the number of trees.
  • Amortized cost: O(log n).

• Note: we have glossed over some details in the analysis. See the original paper or the description in [Weis2007].

Back to MST:

• Recall: with Prim's algorithm
  • n extract-min's.
  • m decrease-key's.

• Thus, for Prim + Fib-heap
        → O(n log(n) + m) bound.

• Compare with:
  • Kruskal: O(m log(n))
          → Dominated by O(m log(m)) sort.
  • Prim + Binary-heap: O(m log(n))
          → O(n log(n)) extract-min's + O(m log(n)) decrease-key's.
  • Boruvka: O(m log(n))
          → From O(log n) phases, each requiring O(m) edge manipulations.

A simple improvement with Boruvka's algorithm:

• Consider the following algorithm:
  Perform O(loglog n) phases of Boruvka (with contractions).
        → This takes O(m loglog(n)) time.
  1. Apply Prim to the resulting graph.
  2. Put together all MST edges into single MST.

• Now, we start with n components (the original nodes as one-node trees).
  • After phase 1, there are at most n/2 components.
  • After phase 2, at most n/2² components.
  • ... after phase k, at most n/2^k components.

• Thus, if we do O(loglog n) phases, we'll have at most n/log(n) components.
        → After contraction, this gives a graph with n/log(n) vertices.

• Applying Prim + Fibonacci on the last graph:
  • O(m + n/log(n) log(n)) = O(m + n) time.
  • Thus, overall: O(m loglog(n)) time.
          → Fastest so far.

Fredman and Tarjan's Algorithm

Fredman and Tarjan didn't stop with inventing the Fibonacci heap [Fred1987].

• Consider Prim+Fib again:
        → O(n log(n)) for n extract-min's and O(m) for m decrease-key's.
  • Even if extract-min can't be improved, we can decrease n
          → Put fewer nodes into the heap.
  • Suppose we try to control the size of the heap?
  • Recall Boruvka: separate components with their own MST's join together eventually
          → The heaps of these components could be kept small.
  • But we don't know how big these components could get.

• Key ideas:

  

  • Fix the heap size.
  • If a component's heap gets too big, abandon growing the component for now.
  • Start another component.

• Fix the heap limit as k (for now).

• We will redefine a Boruvka phase as follows:

      1.  Grow trees until all heaps reach k-limit.
      2.  Contract all trees to get new graph G'
      3.  Set G = G' and repeat 
      

• Another insight:
  • The graphs at successive phases (after contraction) get smaller.
          → We can use different k values in each phase.
  • The more nodes we have, the smaller we should make k.
          → Because, the more the risk of encountering large heaps.

• Let n_i be the number of nodes after (i-1)-st phase (contraction).

• Let k_i be the limit for phase i.
        → Define k_i = 2^2m/n_i

• Then, the running time for a single phase takes
        O(m + n_i log(k_i))
        = O(m + n_i log(2^2m/n_i))
        = O(m) .

• Next, we need to bound the number of phases.

• To do this, let's estimate the number of trees in phase i:
  • Since we stop trees when heap-size is k_i, each tree "touches" k_i edges (which are in the heap).

    

  • Thus
          # trees x k_i ≤ 2m
          → # trees ≤ 2m / k_i
          → n_i+1 ≤ 2m / k_i (because # trees = # nodes at next level of contraction)
          → k_i+1 = 2^2m/n_i+1 ≥ 2^k_i.
          → The k_i's are growing.

• The k_i's can only grow as large as n.

• Definition: log⁽ⁱ⁾(n) is i- repeated logs of n:

  

• Definition: log^*(n) is the number of times you need to take repeated log's to reach 1.

  

• Now, let's work backwards from n.
        k_i ≥ n
        if log⁽ⁱ⁾k_i ≥ log⁽ⁱ⁾n
        which will be true if log⁽ⁱ⁾2m/n_i ≥ log⁽ⁱ⁾n
        which will be true if 2m/n_i ≥ log⁽ⁱ⁾n
        which will be true if 2m/n ≥ log⁽ⁱ⁾n
        which will be true if m/n ≥ log⁽ⁱ⁾n

• Definition: Define β(m,n) = min_i log⁽ⁱ⁾(n) ≤ m/n.

• Thus, there are at most β(m,n) phases.

• Note: β(m,n) ≤ log^*(m/n).