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
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;
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|
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
can be represented as the union of three rectangles. The question whether a
can be compressed to at most k rectangles is NP-complete. Show that, if we
k a fixed parameter, then the problem is fixed parameter tractable, that
is, the problem can be solved in time O(f(k) nc) for some fixed
constant c not depending on k. Hint: Show that
if two consecutive rows, or two consecutive columns, are different, then there must be a border
of a rectangle between them.