Assignment VI

Due date Monday Dec.1.

1. From text: problems 7.1 and 7.2

2. From text: 7.19: show that double satisfiability is NP-complete. Recall that this requires that you prove: a) that the problem is in NP, and b) that a known NP-complete problem can be reduced to it.

3. Complete the proof of 7.26, which we discussed in class, that is to say show how to make an instance of this game that solves a given 3SAT problem.

4. How many satisfying truth assignments do the following boolean expressions have?

a) x and (y or not x) and (z or not y)

b) (x or y) and ( not (x or z) or (not x and not y))

5. Recall that a Hamiltonian circuit in a graph is a path that returns to its starting node after visiting each node once.
a) A graph that is a square has a Hamiltonian circuit (easy).

b) A a graph that is cube also has a Hamiltonian circuit (a little harder).

c) Show that the following graph has no Hamitonian circuit:
0--0--0
|  |  |
0--0--0
|  |  |
0--0--0
Hint: think about any path that goes through the center node.

6. (Optional): the firehouse problem (to be known in the future as the Bloomberg problem): given a graph G, a maximum distance d, and a number of firehouses f, choose f nodes in G so that no node in G is at a distance (number of edges to be traversed) greater than d from some firehouse. Show that the problem is NP-complete.