Problem 59

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Subgraph selection with different probability

Due: March 29
Points: 3

In the randomized MST algorithm we saw in class, each edge is selected to go into H with probability \(\frac{1}{2}\).

What if we made this probabilitiy slightly lower or slightly higher, for example selecting edges for the subgraph with probability \(\frac{1}{3}\) or \(\frac{4}{5}\) or something else. I don't need you to do the full analysis, but tell me how lowering or raising this probability would affect:

  • The size (nodes, edges) of the random subgraph H
  • The size (nodes, edges) of the recursively-computed minimum spanning forest F or H
  • The size (nodes, edges) of the subgraph \(G''\) that results from finding the F-light edges in H
  • The expected running time of a single step in the algorithm.
  • The expected running time of the entire randomized algorithm.

So for each of the things above, say how it would change if the probability were increased or if it were decreased, and why. (Note that many of the above factors are related to each other!)