Question

4.

Show that the Hamiltonian path problem is in NP.

Answer 1

A Hamiltonian path is a simple open path that contains each vertex in a graph exactly once. The HAMILTONIAN PATH problem is the problem to determine whether a given graph contains a Hamiltonian path To show that this problem is NP-complete we first need to show that it actually belongs to the dass NP and then find a known NP-complete problem that can be reduced to HAMILTONIAN PATH For a given graph G we can solve HAMILTONIAN PATH by nondeterministically choosing edges from G that are to be included in the path. Then we traverse the path and make sure that we visit each vertex exactly once. This obviously can be done in polynomial time, and hence, the problem belongs to NP Now we have to find an NP-complete problem that can be reduced to HAMILTONIAN PATH. A closely related problem is the problem to determine whether a graph contains a Hamiltonian cyde, that is, a Hamiltonian path that begin and end in the same vertex. Moreover, we know that HAMILTONIAN CYCLE is NP-complete, so we may try to reduce this problem to HAMILTONIAN PATH Given a graph G- (V, E) we con struct a graph G such that G contains a Hamiltonian cy de if and only if G contains a Hamiltoni an path. This is done by choosing an arbitrary vertex u in G and adding a copy, u, of it together with all its edges. Then add vertices v and u to the graph and connect with u and with u'; see Figure 1 for an example. Figur 1: A graph G and the hamiltoni an path reduced graph G

Suppose first that G contains a Hamiltonian cydle. Then we get a Hamiltonian path in G if we start in v, follow the cycle that we got from G back to u' instead of u and finally end in v'. For example, consider the left graph, G, in Figure 1 which contains the Hamiltonian cyde 1,2,5,6, 4,3,1. In G this corresponds to the path v, 1,2,5,6, 4,3, 1',v' Conversely, suppose G contains a Hamiltonian path. In that case, the path must necessarily have endpoints in v and v. This path can be transformed to a cyde in G. Namely, if we disregard v and v', the path must have endpoints in u and u' and if we remove u' we get a cycle in G if we close the path back to u instead of u' The construction won't work when G is a single edge, so this has to be taken care of as a special case. Hence, we have shown that G contains a Hamiltoni an cy dle if and only if G contains 0 a Hamiltoni an path, which condudes the proof that HAMILTONIAN PATH is NP-complete. D