CSE 5311 Fall 1999

**Quiz #13**

- 1.
- (15 points).
Prove that King Arthur's problem is NP-Complete. Given n knights and the
condition that some pairs of knights are enemies (input is knights and pairs
of enemies), is it possible to arrange the knights around a
round table so that no pair of knights who are enemies sit side by side?
You may use the fact that the Hamiltonian Cycle is NP-Complete to assist your proof: the Hamiltonian Cycle problem determines if there exists a simple cycle in a graph visiting each vertex exactly once.

- 2.
- (5 points). Explain why the ApproxTSPTour algorithm given in class has a ratio bound of 2, and state the graph constraint that must hold for this algorithm to produce an accurate answer.