Homework 12

Due Friday, March 6 at 5:00 PM. Please refer to the homework policy here.

Problems

It looks like a lot of subproblems, but they are very closely related and some are warmup questions that are much easier than others. Some of the problems may have brief answers.

  1. In the Hamiltonian cycle problem, one is given a graph, and the goal is to find a Hamiltonian cycle; that is, a cycle in the graph that contains every vertex exactly once. This problem is interesting both for directed graphs (the "directed Hamiltonian cycle" problem) and undirected graphs (the "undirected Hamiltonian cycle" problem).

    1. Give a polynomial time reduction from - Hamiltonian path (discussed in class) to Hamiltonian cycle (thus showing that directed Hamiltonian cycle is at least as hard as directed Hamiltonian path, which we showed was at least as hard as SAT.)
    2. Give a polynomial time reduction from undirected Hamiltonian cycle to directed Hamiltonian cycle.
    3. Give a polynomial time reduction from directed Hamiltonian cycle to undirected Hamiltonian cycle.
    4. Give a polynomial time reduction from directed Hamiltonian path to undirected Hamiltonian path.
  2. Prove the following problems are at least as hard as SAT.

    1. Given an undirected graph , does have a spanning tree with 2 leaves?
    2. Given an undirected graph , does have a spanning tree with maximum degree 2?
    3. Given an undirected graph , does have a spanning tree with at most 42 leaves?
    4. Given an undirected graph , does have a spanning tree where the maximum degree of any vertex is at most 42?
  3. Let be an undirected graph. A coloring is an assignment of colors (red, blue, green, ...; or just integers ) to each vertex such that any two vertices have distinct colors (integers). Of course an -vertex graph can always be colored with colors (one per vertex). It is natural to ask for the minimum number of colors needed to color the graph. (For example, in many resource allocation problems, each color represents another expensive resource, and an edge between vertices means that that the two vertices cannot share the resource.) The -coloring problem is to decide whether or not has a -coloring, for fixed .

    1. Read the reduction from 3SAT to 3-coloring in either section 12.10 of Jeff's notes or section 8.7 of KT.
    2. Give a polynomial time reduction from 3-coloring to -coloring, for given .
    3. For fixed , suppose you had a polynomial time subroutine that takes as input (only) an undirected graph and returns TRUE/FALSE depending on whether or not the graph is -colorable. Give a polynomial time algorithm that, given a -colorable graph , produces a -coloring.
    4. What about 2-coloring? Either show that 2-coloring is as hard as SAT, or (briefly) describe a polynomial time algorithm for 2-coloring.