Exercises
- KT, Ch. 13, Exercises 6 and 7.
-
This problem concerns a randomized algorithm for coloring graphs.
Assume we have a graph, \( G=(V,E) \), and colors, \( \{ 1,2,3,4\} \).
Then \( f\colon V \rightarrow \{ 1,2,3,4\} \) is called a 4-coloring of \( G \).
We say that an edge \( uv\in E \) is good with respect to \( f \) if
\( f(u)\not= f(v) \).
- Suppose that each vertex independently gets color \( i \) with probability \( 1/4 \) for \( i\in \{ 1,2,3,4\} \). Let the random variable \( X \) be the number of edges in \( E \) that are good with respect to the coloring \( f \). Show that \( E[ X ] = \frac{3|E|}{4} \).
- Use the result above and the probabilistic method to conclude that every graph has a 4-coloring \( f \) such that at least \( \frac{3|E|}{4} \) of its edges are good with respect to \( f \).
- Define a randomized algorithm that, for a given graph \( G=(V,E) \), finds a 4-coloring \( f^* \) of \( V \) such that at least \( \frac{3|E|}{4} \) of the edges of \( G \) are good with respect to \( f^* \).
- Follow the construction from MAX 3-SAT to compute a bound on the expected running time of your algorithm.
- KT, Ch. 13, Exercise 2. Revisit this exercise to also find some upper bound on the probability of at least 1000 Democrats voting for the R candidate.
- KT, Ch. 13, Exercise 8. Practice the construction from MAX 3-SAT again in this slightly harder set-up. Choosing \( k \) uniformly at random works.