CSE 5311 Fall 1999
- (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.
- (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.