Homework 5 Solution set

15-212, Spring 1998

Part 1

1. TSP: ADEBC = 18

2. Number the nodes from top left to lower right, going across the rows:

 1  2  3  4  5
 6  7  8  9 10
   11    12
13 14 15 16 17
18 19 20 21 22

Everything but the Clique has a few possible answers.
HC: 1-2-3-4-5-10-17-22-21-16-12-9-8-7-11-14-15-20-19-18-13-6-1
Clique(3): 1-2-6 or 2-6-7
IS: 1, 3, 5, 7, 9, 13, 15, 17, 19, 21
NC: 2, 4, 6, 7, 8, 9, 10, 12, 14, 18, 20, 22
 

Part 2

This turned out to be a very difficult problem. To prove that the Hamilton Path problem is NP complete, you must do two things:

1. Prove that the Hamilton Path problem is in NP. This is simple: Because you can non-deterministically guess a solution to the problem (a permutation of the nodes) and check in polynomial time (check if there is a path between them) the Hamilton Path problem could be solved by a non-deterministic Turing Machine in polynomial time. Thus, it is a member of NP.

2. Show that another known NP-complete problem can be polynomially reduced to the Hamilton Path problem. In this case, we are reducing the Hamilton Cycle problem to it. The idea is to modify an instance of the Hamilton cycle (such as graph G to the left) to create an instance of the Hamilton Path problem (some graph G'). Graph G' should have a Hamilton path if and only if graph G has a Hamilton cycle.

We can create such a graph through the following process:
 
 
1. Choose a node on the graph G at random. Note that all nodes of the graph would be part of a Hamilton Cycle, so we can select any node without loss of generality.
2. Replace this node with 2 nodes that have the same connections.
3. Create two new nodes, connecting each to one of the nodes produced in step 2. This is the new graph G'.
 

This new graph G' will only have a Hamilton Path if the original graph G had a Hamilton Cycle. If it only had a path (as the example above shows), we've broken it by requiring that we get back to our newly-added nodes.
 
 

Part 3

This reduction was somewhat easier. The example suggested looking at the original NP-completeness proof for the Traveling Salesman problem, where Lewis and Papadimitriou reduce the Hamilton Cycle problem to the Traveling Salesman problem with the following mapping: Create a graph with the same nodes as the Hamilton Cycle problem, but make it fully connected. Assign weights according to the following rule:
  1. If two nodes are connected in graph G, then assign their connecting edge weight 1 in the TSP.
  2. If two nodes are not connected in graph G, then assign their connecting edge weight 2 in the TSP.
However, imagine that three nodes had the following relationship: distance(A,B) = 1, distance(B,C) = 1, distance(C,A)=2. Such a configuration, unfortunately, does not obey the triangle inequality. However, if we change the value for unconnected nodes to 1.5, then all sets of connected nodes obey the triangle inequality.
 

End of Solutions
written by Darren Mauro (darren@cmu.edu)