Randomized Algorithms (Spring 2010)/Problem Set 3

From EtoneWiki
Jump to: navigation, search

Problem 1 (20 points)

The Collatz conjecture says that if you start with any positive integer , the following deterministic procedure

will eventually get to 1. Since the Collatz conjecture seems to be hard to prove, consider the following randomized version:

Note that in this game, does not have to be an integer.

  1. What is the expected value of as a function of and ?
  2. Show that there is a constant such that is a martingale.
  3. Assuming that , use the Azuma's inequality to get a bound on the probability that for any fixed .

Problem 2 (20 points)

(a)
Consider the theorem of large independent set in Lecture 8. The proof of the theorem describes a probabilistic experiment which generates independent set with large expected cardinality. Now we wish to turn this experiment to a randomized algorithm. Consider the special case that the graph is regular.
Let be a -regular graph (every vertex has exact neighbors) on vertices. Run the following algorithm on :
  1. For each vertex , is chosen to a set independently with probability .
  2. Assuming that is the subgraph of induced by , for each edge , remove one of the vertices from .
Let be the resulting independent set.
Derive an upper bound on the probability that this algorithm finds an independent set smaller than .
(b)
Borrow the idea from the theorem of large independent set to prove a similar result for dominating set (a set of vertices such that every vertex is either in or adjacent to a vertex in ). Prove the following theorem:
Let be a -regular graph on vertices. Then has a dominating set of at most vertices.

(Hint: As the probabilistic experiment for generating an independent set, consider sampling a set of vertices and then altering it to a dominating set.)

Problem 3 (10 points)

Let be a cycle of length , where is an integer, let be a partition of the vertices into pairwise disjoint subsets, each of cardinality . Find a proper bound on that no matter how to partition the into , there must be an independent set of containing precisely one vertex from each .

(Hint: use the Lovasz local lemma.)