Michael Rutherford
Math 480a
Final Project
Syntax:
is_Hamiltonian(graph, proof, ShowPath, MSD)
graph: This is the graph that you are trying to tell whether it is Hamiltonian.
Proof: In either case, if it returns true then the graph is provably Hamiltonian. If it returns false and proof equals true you can be certain it is not Hamiltonian. If proof equals false then it could still be Hamiltonian. Default=True
ShowPath: Shows the Hamiltonian Path if it exists. Default=False
MSD: Only used if proof=false. Tells the heuristic algorithm how long it should look for a solution for.
Default=1000
I implemented a function that returns whether an undirected graph is Hamiltonian. Since the Hamiltonian Cycle problem is NP-complete, I implemented two separate algorithms. The first is a back trace algorithm with pruning, which is guaranteed to find a Hamiltonian cycle if it exists but runs in exponential time. The second algorithm is a heuristic algorithm that is not guaranteed to find a solution if it exists, but runs in low order polynomial time. When is_Hamiltonian is called it first does initial pruning of the graph, finds the max degree vertex, and does global checking. The idea behind pruning is that you want to look at the forced edges of the graph. A forced edge is an edge that must be in the Hamiltonian cycle. It is easy to see that all edges coming out of a degree two vertex must be forced. Now if a vertex has two forced edges then the Hamiltonian cycle must travel in and then out of the vertex on those two edges and hence the other edges can not be in the Hamiltonian Cycle. Hence we can delete them from the graph. First we prune the graph and also check for degree one vertex. If we have a degree one vertex, the graph can not possibly be Hamiltonian. Next, I search for the max degree vertex, which I will use as the vertex to start the algorithm. Next I perform global checking on the graph, which means I look at global properties of the graph and see if it can't be Hamiltonian (check for whether it is connected and if it has equal bipartite sets(if it is bipartite).
The backtrace with pruning algorithm is exactly what it sounds like. It does a depth first search of every possible partial path and at every step tries to prune and also does some simple checking(like if it is a degree one vertex) to see if it can even be Hamiltonian. The pruning is very important because it will reduce the search space, which because of the algorithms exponential running time can save a lot of time. The algorithm terminates when it has found a cycle or tried every single possible path.
The HAM algorithm is a heuristic algorithm that takes advantage of two techniques: cycle extension and rotational Transformations. The basic idea is you start with two vertices that are connected and have them be the starting and endpoint of your current partial path. Then you want to keep trying to extend the partial path by extending it to a neighbor of the either the start or end points that isn't in the graph. If you can form a cycle (aka connect the start and endpoint) you want to do it. If it is Hamiltonian then terminate otherwise do a cycle extension.
This diagram that I have above illustrates the concept of a cycle rotation. Basically you want to take your incomplete cycle and find a free vertex that is a neighbor of one of the vertices in the list and then rearrange the cycle (as shown in the picture above) so that it forms a new path with a new end point and start point. Now if you can't form a cycle and everyone of the neighbors of the endpoint and start point of your path is already in the path, you want to do a rotational transformation.
The figure above illustrates the basic is to use the either the start point and end point which only has neighbors in the path already and rearrange the path such that it has a new starting and end point. You then want to put that path in a queue. If you can not extend the path by cycle extension or adding free vertices then you want to dequeue a path from your queue and then do the above techniques again. The algorithm terminates when it has examined a fixed amount (MSD) of partial paths or has found a Hamiltonian cycle.