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.