CSC 491

We talked about brute force, approximation and parameterization in class.

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [Largest Independent Set, 20pt] We want to improve the running time of the algorithm finding a largest independent set using some observations.

- Suppose all vertices in a graph have degree at most 1. Show that the
largest independent set in the graph has size |V| - |E|.
*Hint*: what does such a graph look like. - Use the observation in (a) to improve the algorithm we saw in class; find the recurrence relation for your modified algorithm.
- On top of b, preprocess the graph by first dealing with vertices of degree at least 3; find the recurrence of the algorithm after adding this preprocessing step.

For both b. and c. include your pseudocode.

2. [Wigderson coloring, 10pt] Wigderson's coloring algorithm finds a 3sqrt(n)
coloring of a 3-colorable graph. Improve the algorithm so it finds a sqrt(8n)
coloring of a 3-colorable graph. *Hint*: modify the degree cut-off.

3. [Coloring planar graphs, 20pt] The four-color theorem tells us that every planar graph, that is a graph that can be drawn in the plane without edges intersecting, can be colored using at most 4 colors. In this exercise we'll see an algorithm that colors planar graphs using at most 6 colors.

- [10pt] Euler's formula states that n + f = 2 + m for a planar graph, where n = |V|, m = |E| and f is the number of faces (regions) of the graph, counting the outer face. E.g., consider the graph in the following picture; it has n = 10, m = 17, f = 9, so n + f = 19 = 2 + m. Using Euler's formula show that a planar graph always has a vertex of degree at most 5. (Hint: assume, for a contradiction, that every vertex has degree at least 6.)

- [10pt] Write pseudocode for a polynomial time algorithm that colors a planar graph using at most 6 colors.
- [Extra Credit] How can you make the algorithm run in time O(|V| + |E|)?

4. [TSP, 20pt] Do Exercise 35.2-3 on page 1033 of the book.

5. [Extra Credit] Given an n x n matrix of zeros and ones, we can try to
compress it by representing it as the union of at most *k* rectangles of
ones. For example, the matrix

ooooooooooooo ooooo111ooooo oo111111111oo oo111111111oo ooooo111ooooo ooooo111ooooo oo111111111oo oo111111111oo ooooo111ooooo ooooooooooooocan be represented as the union of three rectangles. The question whether a given matrix

can be compressed to at most

Marcus Schaefer

Last updated: November 6th, 2oo6.