   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.

Here we offer a solution suggested by the wise magician Merlin.

The King Arthur's problem is in NP: A non-deterministic algorithm guesses a sitting plan, and then verifies if the arrangement results in a pair of knights sitting next to each other. Verification requires only polynomial time.

The King Arthur's problem is NP-hard: We reduce the Hamiltonian Cycle problem to the King Arthur's problem. Given an instance of the Hamiltonian Cycle problem, that is, a graph G, we take each vertex as a knight, and determine that two knights are enemies of each other iff they represent vertices that are not connected by an edge. If G is Hamiltonian, then there is a cycle that visits all vertices. Therefore, there is an arrangement of knights sitting on the round table so that neighbouring knights represents neighbours in the graph. But our construction requires that adjacency implies friendship. So the resulting King Arthur instance will have a solution. Conversely, if there is a solution to the King Arthur instance, then there is an arrangement of vertices in G around the round table so that neighbouring vertices represents friendly knights. However, friendship implies adjacency. The arrangement is in fact a cycle in the graph G. Since the reduction is poly-time computable, the King Arthur's problem is NP-hard.

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.

See class notes.   