A NEW ALGORITHM FOR FINDINGHAMILTONIAN CIRCUITSASHAY DHARWADKER
INSTITUTE OF MATHEMATICS

We present a new polynomialtime
algorithm for finding Hamiltonian circuits in graphs. It is shown that
the algorithm always finds a Hamiltonian circuit in graphs that have at
least three vertices and minimum degree at least half the total number
of vertices. In the process, we also obtain a constructive proof of Dirac’s
famous theorem of 1952, for the first time. The algorithm finds a Hamiltonian
circuit (respectively, tour) in all known examples of graphs that have
a Hamiltonian circuit (respectively, tour). In view of the importance of
the P versus NP question, we ask: does there exist a graph
that has a Hamiltonian circuit (respectively, tour) but for which this
algorithm cannot find a Hamiltonian circuit (respectively, tour)? The
algorithm is implemented in C++ and the program is demonstrated
with several examples [Download].


Thanks to J.R. Manes for
presenting a seminar about this algorithm at the University of Alaska,
Fairbanks, in December 2004. Thanks to Guenter Stertenbrink for spending
many hours testing the program and providing Examples 3.3 in February 2005.
Thanks to Roberto Tauraso and his students at the University
of Rome for using this algorithm to find many large
square loops and providing Examples 3.4 in November 2005. This algorithm has also been cited in
Applications of Graph Theory published by the
Korean Society for Industrial and Applied Mathematics. We are pleased to announce that The Hamiltonian Circuit Algorithm
has been published by Amazon in 2011.


In 1856 [1],
Hamilton described a certain mathematical game called the Icosian
played on the surface of a dodecahedron. Starting from a given vertex,
the objective was to find a path of consecutive vertices along the edges,
visiting every vertex exactly once and returning to the original vertex
to complete a circuit. The general problem of trying to find such Hamiltonian
Circuits in arbitrary graphs turned out to be very difficult to solve.

To begin with, we present basic definitions
about graphs and algorithms following [5]. We
use the usual notation
⌊x⌋
to denote the floor function i.e. the greatest integer not greater
than x and ⌈x⌉
to denote the ceiling function i.e. the least integer not less than
x.
A simple graph G with n vertices consists of a set of vertices V, with V = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. Note that the definition of G explicitly forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite. We may label the vertices of G with the integers 1, 2, ..., n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is a neighbor of v and write uv∈E. Neighborhood is clearly a symmetric relationship: uv∈E if and only if vu∈E. The degree of a vertex v, denoted by d(v), is the number of neighbors of v. The minimum degree over all vertices of G is denoted by δ. The adjacency matrix of G is an n×n matrix with the entry in row u and column v equal to 1 if uv∈E and equal to 0 otherwise. A path P in G is a sequence of distinct vertices v_{1}, v_{2}, ..., v_{k} such that v_{i}v_{i}_{+1}∈E for i = 1, 2, ..., k1. Given a path P, its sequence of distinct vertices v_{1}, v_{2}, ..., v_{k} are said to have been visited and any vertex w outside P is said to be unvisited. Given a path P and a vertex v, the number of unvisited neighbors of v is denoted by η(v). A path P in G visiting vertices v_{1}, v_{2}, ..., v_{k} is called a Hamiltonian tour if k = n. Thus, a Hamiltonian tour in a simple graph is a path that visits every vertex exactly once. A path P in G visiting vertices v_{1}, v_{2}, ..., v_{n} is called a Hamiltonian circuit if it is a Hamiltonian tour and v_{1}v_{n}∈E. Thus, a Hamiltonian circuit in a simple graph is a path that visits every vertex exactly once and then allows us to return to the beginning of the path via an edge. If the simple graph G has a Hamiltonian circuit, G is said to be a Hamiltonian graph. An algorithm is a problemsolving method suitable for implementation as a computer program. While designing algorithms we are typically faced with a number of different approaches. For small problems, it hardly matters which approach we use, as long as it is one that solves the problem correctly. However, there are many problems for which the only known algorithms take so long to compute the solution that they are practically useless. A polynomialtime algorithm is one whose number of computational steps is always bounded by a polynomial function of the size of the input. Thus, a polynomialtime algorithm is one that is actually useful in practice. The class of all such problems that have polynomialtime algorithms is denoted by P. For some problems, there are no known polynomialtime algorithms but these problems do have nondeterministic polynomialtime algorithms: try all candidates for solutions simultaneously and for each given candidate, verify whether it is a correct solution in polynomialtime. The class of all such problems is denoted by NP. Clearly P⊆NP. On the other hand, there are problems that are known to be in NP and are such that any polynomialtime algorithm for them can be transformed (in polynomialtime) into a polynomialtime algorithm for every problem in NP. Such problems are called NPcomplete. The problem of finding a Hamiltonian circuit (respectively, tour) is known to be NPcomplete [3]. Thus, if we are able to show the existence of a polynomialtime algorithm that finds a Hamiltonian circuit (respectively, tour) in every graph that has a Hamiltonian circuit (respectively, tour), we could prove that P = NP. The present algorithm is, so far as we know, a promising candidate for the task. One of the greatest unresolved problems in mathematics and computer science today is whether P = NP or P ≠ NP [4]. 
We are now ready to present a formal description
of the algorithm. This is followed by a small example illustrating the
steps of the algorithm.
3.1. Algorithm. Given as input a simple graph G with n vertices. Label the vertices 1, 2, ..., n in descending order of degrees d(1) ≥ d(2) ≥ ... ≥ d(n). For each initial vertex u = 1, 2, ..., n in turn, perform Parts I, II and III as follows:
First perform Part I. To initialize (Iteration 1), we select v_{1}=
1 and let the path of visited vertices be v_{1} = 1. The
unvisited neighbors of v_{1} = 1 are 2, 5 and 6. The vertex
2 has two unvisited neighbors 3 and 8, so η(2)
= 2; the vertex 5 has two unvisited neighbors 3 and 4, so η(5)
= 2; the vertex 6 has two unvisited neighbors 7 and 8, so η(6)
= 2. Here vertex 2 has the smallest label such that η(2)
= 2 is a minimum. At Iteration 2, select v_{2} = 2 and let
the path of visited vertices be v_{1} = 1, v_{2}
= 2. The unvisited neighbors of v_{2} = 2 are 3 and 8. The
vertex 3 has two unvisited neighbors 4 and 5, so η(3)
= 2; the vertex 8 has two unvisited neighbors 6 and 7, so η(8)
= 2. Here vertex 3 has the smallest label such that η(3)
= 2 is a minimum. At Iteration 3, select v_{3} = 3 and let
the path of visited vertices be v_{1} = 1, v_{2}
= 2, v_{3} = 3. The unvisited neighbors of v_{3}
= 3 are 4 and 5. The vertex 4 has only one unvisited neighbor 5, so η(4)
= 1; the vertex 5 also has only one unvisited neighbor 4, so η(5)
= 1. Here vertex 4 has the smallest label such that η(4)
= 1 is a minimum. At Iteration 4, select v_{4} = 4 and let
the path of visited vertices be v_{1} = 1, v_{2}
= 2, v_{3} = 3, v_{4} = 4. The only unvisited
neighbor of v_{4} = 4 is 5. The vertex 5 has no unvisited
neighbors, so η(5) = 0. We select v_{5}
= 5, and let the path of visited vertices be v_{1} = 1,
v_{2}
= 2, v_{3} = 3, v_{4} = 4, v_{5}
= 5. Part I terminates with the resulting path
P^{(0)} visiting
vertices v_{1} = 1, v_{2} = 2, v_{3}
= 3, v_{4} = 4, v_{5} = 5 and cardinality
k^{(0)}
= 5.
3.3. Example. Provided by Guenter Stertenbrink, February 2005
[Download].
This example shows that it is necessary to order the vertices by descending
degrees and Parts II(b) and II(c) are also used.
3.4. Example. Provided by Roberto Tauraso, November 2005 [Download].
This example shows how the algorithm works in the exceptional cases (a)
and (b).
A square loop of size n is a circular arrangement of the integers 1, 2, ..., n such that the sum of any two adjacent integers is a perfect square. Define a graph G_{n} with vertices 1, 2, ..., n such that there is an edge between vertex i and vertex j if and only if i+j is a perfect square. Then a Hamiltonian circuit in G_{n} is exactly a square loop of size n. The graph of figure 3.3 shows a Hamiltonian circuit in G_{32} and a square loop of size 32. Roberto Tauraso and his students at the University of Rome computed many large square loops using this algorithm and conjecture that square loops exist for all n ≥ 32. 
We shall now show that the above algorithm
terminates in polynomialtime, by specifying a polynomial of the number
of vertices n of the input graph, that is an upper bound on the
total number of computational steps performed by the algorithm. Note that
we consider
4.1. Proposition. Given as input a simple graph G with n vertices, the algorithm takes less than 4n^{5}+8n^{4}+3n^{3}+2n^{2}+n steps to terminate. Proof. Given an initial vertex u, first consider Part
I of the algorithm. At iteration r, it takes less than n
steps to determine the unvisited neighbors v^{(r)}_{1},
..., v^{(r)}_{m} of v_{r}.
Then for each v^{(r)}_{i} it takes
less than n steps to determine the unvisited neighbors of v^{(r)}_{i}
and hence find η(v^{(r)}_{i}).
Thereafter it takes less than n steps to find the minimum of the
integers η(v^{(r)}_{1}),
..., η(v^{(r)}_{m}).
Thus we count a total of less than n^{2}+n steps
at iteration r. There are at most n iterations, so a total
of less than n(n^{2}+n) = n^{3}+n^{2}
steps terminates Part I to find path P^{(0)}.
4.2. Remark. A simple graph G with n vertices can have at most n(n1)/2 edges. In the exceptional case (b), the algorithm will run once for each edge, so the running time of the program will increase at most by a factor of O(n^{2}). 
The algorithm may be applied to any simple
graph and will always terminate in polynomialtime. The theorem below establishes
a sufficient condition on the input graph which guarantees that the algorithm
will find a Hamiltonian circuit. As a corollary we obtain a constructive
proof of Dirac's theorem [2]. For the proof of
the theorem, we shall need the following lemma that is a direct consequence
of the
5.1. Pigeonhole Principle. If l letters are distributed into p pigeonholes and l > p ≥ 1, then some pigeonhole must receive at least two letters. 5.2. Lemma. Let G be a simple graph with n ≥ 3 vertices and δ ≥ n/2. If X is a subset with ⌈n/2⌉ vertices and v is a vertex outside X then v must have a neighbor in X. Proof. If n = 3, X must consist of the two vertices
other than v and since d(v) ≥ 2
both vertices in X must be neighbors of v. Let n > 3
and suppose v has no neighbors in
X. Then since d(v) ≥ n/2,
there are at least l = ⌈n/2⌉
edges (letters) with one end vertex v and the other end vertex among
the p = n1⌈n/2⌉ ≥ 1
vertices (pigeonholes) excluding v and X. Since l > p,
the pigeonhole principle implies that some pigeonhole vertex must receive
at least two edges with the other end vertex being v. This contradicts
the fact that G is simple and has no multiple edges. Thus v
must have a neighbor in X. ☐
5.3. Theorem. If G is a simple graph with n ≥ 3 vertices and δ ≥ n/2, then the algorithm finds a Hamiltonian circuit in G. Proof. Label the vertices of the graph G as 1, 2, ...,
n. Start at any initial vertex u. We first show that the
path P^{(0)} produced by Part I contains more than ⌈n/2⌉
vertices. Consider the iterations of Part I.
5.4. Corollary. (Dirac 1952, [2]). As an immediate consequence of the theorem, if G is a simple graph with n ≥ 3 vertices and δ ≥ n/2, then G is Hamiltonian. 5.5. Question. Let G be a simple graph with n vertices. The theorem shows that Dirac’s conditions n ≥ 3 and δ ≥ n/2 are sufficient for the algorithm to find a Hamiltonian circuit in G. Examples 3, the Platonic graphs in section 7 and the reentrant knight's tours in section 8 show that Dirac’s conditions are not necessary for the algorithm to find a Hamiltonian circuit in G. All the known examples show that whenever a graph G has a Hamiltonian circuit (respectively, tour), the algorithm finds a Hamiltonian circuit (respectively, tour) in G.

We provide a C++ program, hamilton.cpp,
in the style of [6], that implements the algorithm,
together with sample input/output files.
6.1. Program. The following program will make a simple console
application, and is included in the Demonstration Program package. The
program was tested using Microsoft
™ Visual
C++ 6.0.
6.2. Input File. The input file for the program, graph.txt,
has as first entry the number of vertices of the graph, followed by white
space, followed by the entries of the adjacency matrix of the graph in
rowmajor order, all separated by white space. We use the graph of Example
3.2.
6.3. Output File. The output file for the program, paths.txt,
lists the paths, tours and circuits found by the algorithm.

Convex polyhedra with faces composed of
congruent convex regular polygons are called Platonic solids. In
the last Book of the Elements, Euclid [9] proved
that there are exactly five platonic solids as described by Plato [10]:
the tetrahedron, the octahedron, the cube, the icosahedron and the dodecahedron.
The graphs consisting of vertices and edges of the platonic solids are
Hamiltonian. We run the program for the graphs of the five platonic solids
and show the first Hamiltonian circuit found by the algorithm in each case.
For more details, input/output files and visualization see the demonstration
program.

A simple graph G with n
vertices that satisfies Dirac's conditions n ≥ 3
and δ ≥ n/2 is called a Dirac Graph.
By theorem 5.3, we know that the algorithm will always find a Hamiltonian
circuit in a Dirac graph. We run the program for a small and a large Dirac
graph, showing in each case the first Hamiltonian circuit found. For more
details, input/output files and visualization, see the demonstration
program.

In 840 A.D., alAdli [7],
a renowned shatranj (chess) player of Baghdad is said to have discovered
the first reentrant knight's tour, a sequence of moves that takes
the knight to each square on an 8 × 8
chessboard exactly once, returning to the original square. Many other reentrant
knight's tours were subsequently discovered but Euler [8]
was the first mathematician to do a systematic analysis in 1766, not only
for the 8×8 chessboard, but for reentrant
knight's tours on the general n×n
chessboard. Given an
n×n
chessboard, define a knight's graph with a vertex corresponding
to each square of the chessboard and an edge connecting vertex
i
with vertex j if and only if there is a legal knight's move from
the square corresponding to vertex i to the square corresponding
to vertex j. Thus, a reentrant knight's tour on the chessboard
corresponds to a Hamiltonian circuit in the knight's graph. We run the
program on the knight's graphs corresponding to chessboards of dimensions
8×8, 20×20,
40×40 and show the first reentrant knight's
tour found by the algorithm in each case. For more details, input/output
files and visualization, see the demonstration program.

Copyright © 2004 by Ashay Dharwadker. All rights reserved.