Summary: CMPSCI 711: Really Advanced Algorithms
Problem Set 3 Out: April 1, 2003
Due: April 10, 2003
1. [MR95] Problem 6.1.
2. Given an n vertex graph that is 4-colorable, we want to nd an assignement of 2 colors to the vertices
that has the property that there is no monochromatic clique of size 4. Consider the following random-
ized process: while there exists a clique of size 4 that is monochromatic, choose any such clique, and
ip the color of a randomly chosen vertex in the clique. Assuming that you start with a graph that is
4-colorable and an arbitrary assignment of 2 colors to the vertices of that graph, give an upper bound
on the expected number of color
ips required until we have an assignment using 2 colors that has the
3. [MR95] Problem 6.8.
4. In lecture, we saw a saw an Integer Programming formulation of the Vertex-Cover problem. Use
the Linear Programming relaxation of this problem, as well as a rounding procedure to obtain a
2-approximation to this problem.
5. In the Set-Cover problem, we are given sets C 1 ; C 2 ; : : : ; Cn , where the same element may appear in
more than one of the sets. We want to determine the minimum sized collection of sets fC i 1
: : : C i k g
required to ensure that every element of [ n