Search for Hamiltonian Cycles

Csongor Gy. Csehi
János Tóth

Determining whether Hamiltonian cycles exist in graphs is an NP-complete problem, so it is no wonder that the Combinatorica function HamiltonianCycle is slow for large graphs. Theorems by Dirac, Ore, Pósa, and Chvátal provide sufficient conditions that are easy to check for the existence of such cycles. This article provides Mathematica programs for those conditions, thus extending the capability of HamiltonianQ, which only tests the biconnectivity—a simple necessary condition—of a given graph. We also investigate experimentally the limiting behavior of whether the conditions are fulfilled for large random graphs. The phenomenon seen is proved as a theorem, closely related to earlier results by Karp and Pósa.

Introduction

The Combinatorica function HamiltonianCycle seems to work slowly for large graphs, because finding a Hamiltonian cycle in graphs is obviously an NP-complete problem. The search can be made faster, starting by testing if such a cycle exists at all. The Combinatorica function HamiltonianQ does this by checking the biconnectivity of the graph, which is a simple necessary condition for the existence of a Hamiltonian cycle. However, further conditions are easy to check, formulated in theorems by Dirac [], Ore [], Pósa [], and Chvátal []. (See also [, , ].) It saves time to apply these criteria before trying to construct a Hamiltonian cycle. We think that the present algorithms might also help improve other functions in the Combinatorica Package, such as TravelingSalesman.

All of our algorithms are deterministic; however, probabilistic algorithms are also known for the same problem, see Angluin and Valiant [].

The structure of our paper is as follows. First we define the functions that test the conditions in the theorems by Dirac, Ore, Pósa, and Chvátal and we apply these functions to all the graphs in FiniteGraphs. Two examples are shown to prove that the conditions are different. Next, a few examples are used to show that in some cases the HamiltonianCycle function takes more time than one of our functions using the simplest necessary condition. Experiments on large Erdős–Rényi random graphs G(n,p) as n (the number of vertices) tends to infinity follow, leading to a conjecture that if p>(1/2) (p is the probability of an edge), then the conditions are typically fulfilled, and if p<(1/2), then they are typically violated. This is in accordance with the results of Pósa [] and Karp (see []). The conjecture is finally rigorously proved and also illustrated.

Functions

We need these two packages.

Get["Combinatorica`"]//Quiet;
Get["GraphUtilities`"];

First of all, the function RequireQ verifies the necessary condition that all of the vertices of the graph should have at least two neighbors.

RequireQ[G_]:=Min[Degrees[G]]≥2;

Next we test four sufficient conditions formulated as in [].

Dirac’s theorem

A simple graph with n⩾3 graph vertices in which each vertex has degree at least ⌈(n/2)⌉ has a Hamiltonian cycle.

DiracQ[G_]:=V[G]⩾3&&And@@Map[#⩾Ceiling[V[G]/2]&,Degrees[G]]

Ore’s theorem

If a simple graph G has n⩾3 graph vertices and every pair of vertices that are not joined by an edge has a sum of degrees that is greater than n, then G has a Hamiltonian cycle.

OreQ[G_]:=Module[{d=Degrees[G],adj=AdjacencyMatrix[G]},
And@@Flatten[Table[Or[adj[[i,j]]==1,d[[i]]+d[[j]]≥V[G]],{i,V[G]},{j,i+1,V[G]}]]]

Pósa’s theorem

If a simple graph G has degrees (Subscript[d, 1])⩽(Subscript[d, 2])…⩽(Subscript[d, n]) where n⩾3 and (Subscript[d, k])⩾k+1 if k<(n/2), then G has a Hamiltonian cycle.

PosaQ[G_]:=
Module[{dord=Sort@Degrees[G],n=V@G},
n⩾3&&And@@Map[dord[[#]]≥#+1&,Range[(Ceiling@(n/2))-1]]]

Chvátal’s theorem

If a simple graph G has degrees (Subscript[d, 1])⩽(Subscript[d, 2])…⩽(Subscript[d, n]) where n⩾3 and, when (Subscript[d, k])≤k<(n/2), then (Subscript[d, n-k])⩾n-k holds, then G has a Hamiltonian cycle.

ChvatalQ[G_]:=
Module[{dord=Sort@Degrees[G],n=V@G},
n⩾3&&And@@Map[(dord[[#]]>#)∨(dord[[n-#]]≥n-#)&,Range[(Ceiling@(n/2))-1]]]

Examples

In these examples we can see the usefulness of the theorems.

AbsoluteTiming[RequireQ[#]&/@FiniteGraphs]
AbsoluteTiming[DiracQ[#]&/@FiniteGraphs]
AbsoluteTiming[OreQ[#]&/@FiniteGraphs]
AbsoluteTiming[PosaQ[#]&/@FiniteGraphs]
AbsoluteTiming[ChvatalQ[#]&/@FiniteGraphs]

These functions run fast, but AbsoluteTiming[(HamiltonianCycle[#1]&)/@FiniteGraphs] would take 10 hours. That shows that the Hamiltonian cycles are found (10^5) times more slowly than the theorems compute which graphs surely have a Hamiltonian cycle. If one has many large graphs but needs only a single Hamiltonian cycle in any one of them, these functions should be run first.

In the following individual examples, HamiltonianCycle runs 10 times more slowly than the theorems. The difference grows with the size of the graphs because searching for Hamiltonian cycles is an O(n!) complexity problem and the complexity of the theorems is only O((n^2)).

GraphPlot[m1={{0,1,1,0,1,1},{1,0,0,1,1,1},{1,0,0,1,1,1},{0,1,1,0,0,0},{1,1,1,0,0,0},{1,1,1,0,0,0}}]
G1=FromAdjacencyMatrix[m1];
Map[AbsoluteTiming[#@G1]&,{DiracQ,OreQ,PosaQ,ChvatalQ,HamiltonianCycle}]
GraphPlot[m2={{0,1,1,0,1,1,0,1,0},{1,0,0,1,1,1,1,0,1},{1,0,0,1,1,1,0,1,0},{0,1,1,0,0,0,1,0,0},{1,1,1,0,0,0,0,0,1},{1,1,1,0,0,0,1,1,0},{0,1,0,1,0,1,0,1,1},{1,0,1,0,0,1,1,0,0},{0,1,0,0,1,0,1,0,0}}]
G2=FromAdjacencyMatrix[m2];
Map[AbsoluteTiming[#@G2]&,{DiracQ,OreQ,PosaQ,ChvatalQ,HamiltonianCycle}]

These two examples also illustrate that the theorems do not always give the same result. However it is easy to see the connection between Dirac’s theorem and Ore’s theorem, because satisfying the conditions of Dirac’s theorem implies that the conditions of Ore’s theorem are also satisfied. There are more implications between these theorems, which are not as easy to prove: the conditions of Ore’s theorem imply those of Pósa’s theorem and the conditions of Pósa’s theorem imply those of Chvátal’s theorem.

A graph G is biconnected if for every two vertices u and v of G, there are two disjoint simple paths between u and v. The built-in function HamiltonianQ only tests the biconnectivity of the graph, and if the graph is biconnected, it runs the HamiltonianCycle function. So if the graph is biconnected then it is slower than the theorems. The RequireQ function may provide a negative result more quickly.

AbsoluteTiming[RequireQ[FiniteGraphs[[25]]]]
AbsoluteTiming[HamiltonianCycle[FiniteGraphs[[25]]]]
AbsoluteTiming[HamiltonianQ[FiniteGraphs[[25]]]]

An even more convincing example of the same type follows.

m={
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}};
G=FromAdjacencyMatrix[m];
AbsoluteTiming[RequireQ[G]]
AbsoluteTiming[HamiltonianCycle[G]]
AbsoluteTiming[HamiltonianQ[G]]

Here is an example for the difference in a large graph.

G=RandomGraph[5000,3/5000];
Map[AbsoluteTiming[#@G]&,{RequireQ,HamiltonianQ}]

Here we can see that in huge graphs it is better to run the RequireQ function first, because it is possible that Mathematica will search for a long time when there is no Hamiltonian cycle in the graph at all. So it might be useful to build the function RequireQ into the HamiltonianQ and HamiltonianCycle functions in Mathematica.

Limit Values in Large Graphs

In applying the theorems for large Erdős–Rényi random graphs (see []) using Mathematica, a question emerges: what kinds of limit do exist?

Let p denote the probability of the existence of an edge. We wonder what happens if p is fixed and the number of vertices tends to infinity.

G=RandomGraph[100,58/100];
Map[AbsoluteTiming[#@G]&,{DiracQ,OreQ,PosaQ,ChvatalQ,HamiltonianCycle}]

As can be seen in the previous example, Pósa’s theorem or Chvátal’s theorem is more efficient than the others because they gave True and the others did not, so let us use only these two.

G=RandomGraph[100,48/100];
Map[AbsoluteTiming[#@G]&,{PosaQ,ChvatalQ,GraphPlot}]

G=RandomGraph[100,52/100];
Map[AbsoluteTiming[#@G]&,{PosaQ,ChvatalQ,GraphPlot}]

Our simulation results have shown that in a random graph with a hundred vertices with probability 0.48 for an edge, the conditions of the theorems are violated in about 99.6% of the cases. However, changing the edge probability to 0.52 implies that the conditions of the theorems are satisfied in about 98.8% of the cases.

Let us try these limits in graphs with a thousand vertices.

G=RandomGraph[1000,52/100];
Map[AbsoluteTiming[#@G]&,{PosaQ,ChvatalQ,GraphPlot}]

G=RandomGraph[1000,48/100];
Map[AbsoluteTiming[#@G]&,{PosaQ,ChvatalQ,GraphPlot}]

The ratios seem to be the same, but it is very difficult to compute the relevant probabilities. Here is a table with the test results.

Text@Grid[{{"number of\nvertices","number of\ntest graphs","probability\nof an edge","number of cases\nwhen Pósa’s\ntheorem is true","number of cases\nwhen Chvátal’s\ntheorem is true"},
{100,10000,0.48,0,38},
{100,10000,0.52,8739,9862},
{100,100000,0.48,9,344},
{100,100000,0.52,87620,98780},
{1000,1000,0.48,0,0},
{1000,1000,0.52,1000,1000},
{1000,1000,0.495,0,0},
{1000,1000,0.505,1000,1000},
{1000,1000,0.498,0,5},
{1000,1000,0.502,899,987}},Frame->All]

Theorem

Let p be the probability of an edge and ϵ be any positive number. If p-ϵ=(1/2) and n->∞, then the probability of satisfying the conditions of the four theorems tends to 1, and if p+ϵ=(1/2) and n ->∞, then the probability of satisfying the conditions of the four theorems tends to 0.

Proof

Number the vertices with a bijective function N:V->{1,2,…,n}.

When p>(1/2), change the edges of the graph with these rules:

If N(y)>N(x):

Delete the edge if N(x)=N(y)-(n/2).

Direct the edge x->y if N(y)-N(x)<(n/2).

Direct the edge y->x if N(y)-N(x)>(n/2).

We can examine the distribution of in-degrees and out-degrees separately.

With this construction the sum of the in-degree and out-degree for each vertex x is less than or equal to the degree of x in the original graph.

The distribution of in-degrees of x is (({{⌊(n/2)⌋-1}, {p}})) for even n or  (({{⌊(n/2)⌋}, {p}}))  for odd n. Let us work with the worst case.

Binomial(n,p)=(Subscript[X, 1])+(Subscript[X, 2])+…+(Subscript[X, n]), where (Subscript[X, i])=Bernoulli(p) for all i∈ {1,2,…,n}. By the central limit theorem (CLT), α=((Binomial(⌊(n/2)⌋-1,p)-(⌊(n/2)⌋-1)p)/(Sqrt[p(1-p)(⌊(n/2)⌋-1)]))->N(0,1).

It is well known that ((1/x)-(1/(x^3)))((e^((-(x^2))/2))/(Sqrt[2π]))<ℙ(X>x)<(1/x)((e^((-(x^2))/2))/(Sqrt[2π])) for all x>0 if X=N(0,1).

The speed of convergence of the CLT is at least on the order of (1/(Sqrt[n])).

Let β=(((⌊(n/2)⌋-1)p-(n/4))/(Sqrt[p(1-p)(⌊(n/2)⌋-1)])).

Then ℙ(in-degree>(n/4))=ℙ(Binomial(⌊(n/2)⌋-1,p)>(n/4))=ℙ(Binomial(⌊(n/2)⌋-1,p)-(⌊(n/2)⌋-1)p>(n/4)-(⌊(n/2)⌋-1)p)=ℙ(α>(((n/4)-(⌊(n/2)⌋-1)p)/(Sqrt[p(1-p)(⌊(n/2)⌋-1)])))=1-ℙ(α>β)

If p>(1/2), then β>0 for large n, so (((ℙ(Binomial(⌊(n/2)⌋-1,p)>(n/4))))^n)=(((1-ℙ(α>β)))^n)>(((1-(1/β)((e^((-(β^2))/2))/(Sqrt[2π]))))^n) ->1.

(This is because (lim_(n->∞))(((1+(Subscript[a, n])))^n)=(e^((lim_(n->∞))n (Subscript[a, n]))).)

So the probability that all in-degrees are greater than (n/4) tends to 1. We can prove the same for the out-degrees, so all of the degrees will be greater than (n/2) in the original graph. Then the probability of satisfying the conditions of Dirac’s theorem tends to 1 and the same holds for the other three theorems.

When p<(1/2), direct the edges of the graph using the following rules if N(y)>N(x).

Double the edge and direct them in opposite ways, x->y and y->x, if N(x)=N(y)-(n/2).

Direct the edge x->y if N(y)-N(x)<(n/2).

Direct the edge y->x if N(y)-N(x)>(n/2).

With this construction the sum of the in-degree and out-degree for each vertex x is greater than or equal to the degree of x in the original graph.

The distribution of the in-degree of x is Binomial(((n-1)/2),p) if n is odd or Binomial((n/2),p) if n is even. Let us work with the worst case.

Let δ=((Binomial((n/2),p)-(n/2)p)/(Sqrt[p(1-p)(n/2)])) and γ=(((n/4)-1-(n/2)p)/(Sqrt[p(1-p)(n/2)])).

Then Ρ(in-degree<(n/4)-1)=ℙ(Binomial((n/2),p)<(n/4)-1)=ℙ(Binomial((n/2),p)-(n/2)p<(n/4)-1-(n/2)p)=ℙ(δ<γ)=1-ℙ(δ>γ).

If p<(1/2), then γ>0 for large n, so
(((ℙ(Binomial(n-1,p)<(n/4)-1)))^n)=(((1-ℙ(δ>γ)))^n)>(((1-(1/γ)((e^((-(γ^2))/2))/(Sqrt[2π]))))^n) ->1.

So the probability that all the in-degrees are less than (n/4)-1 tends to 1. We can prove the same for the out-degrees, so all degrees will be less than (n/2)-2 in the original graph.

Then the probability of satisfying the conditions of Chvátal’s theorem tends to 0, and the same holds for the other three theorems. ■

Some illustrations of the proof follow.

Here we can see that the distribution of the degrees is near to Binomial(n-1,p), where n is the number of the vertices and p denotes the probability of the existence of an edge.

L=Degrees[RandomGraph[100,0.6]];
Show[{Histogram[L,{40,80,1},AxesLabel->{"degrees","number of\n vertices"}],ListLinePlot[Table[{k,100*PDF[BinomialDistribution[100-1,0.6],k]},{k,42,77}],PlotStyle->Red]}]

L=Degrees[RandomGraph[1000,0.6]];
Show[Histogram[L,{520,670,1},AxesLabel->{"degrees","number of\n vertices"}],ListLinePlot[Table[{k,1000*PDF[BinomialDistribution[1000-1,0.6],k]},{k,520,670}],PlotStyle->Red]]

Let ϵ>0; if we fix p=(1/2)-ϵ (or p=(1/2)+ϵ) and the number of vertices tends to infinity, then ℙ(all of the degrees are greater (or less) than  (n/2))->1.

Manipulate[Show[{Plot[Binomial[n-1,i]((((1/2)+ϵ))^i)((((1/2)-ϵ))^(n-1-i)),{i,0.4n,0.6n},PlotRange->All,ImageSize->{400,300},ImagePadding->{{15,Automatic},{Automatic,Automatic}}],Graphics[{Thick,Red,Line[{{(n/2),0},{(n/2),(1/(Sqrt[n]))}}]}]}],
{n,100,10000,Appearance->"Labeled"},
{{ϵ,0.05},-0.1,0.1,Appearance->"Labeled"}]

Our results are related to some earlier results.

R. M. Karp (see []): G(n,p) is Hamiltonian with probability 1-o(1) if p≥15.96log((n/(n-1))).

L. Pósa []: Almost all graphs with n vertices and c n log(n) edges are Hamiltonian.

With these theorems it is easy to see that if p>(1/2) and n->∞, then the probability that G(n,p) is Hamiltonian tends to 1. Moreover these theorems imply that if p is independent of n and n->∞, then the probability that G(n,p) is Hamiltonian tends to 1.

The experiments show that the theorems are not only useful, but also raise interesting questions.

Acknowledgments

I wish to thank Gábor Wiener and Gábor Borbély for stimulating discussions and suggestions. The help of Ágnes Tóth both in programming and theory is highly appreciated. I am grateful to Daniel Lichtblau and Ambrus Zsbán, who gave ideas for the proof.

References

G. A. Dirac, “Some Theorems on Abstract Graphs,” Proceedings of the London Mathematical Society, 2, 1952 pp. 69–81. www.plms.oxfordjournals.org/content/s3-2/1/69.extract.

O. Ore, “Note on Hamiltonian Circuits,” American Mathematical Monthly, 67, 1960 p. 55.

L. Pósa, “A Theorem Concerning Hamilton Lines,” Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közlemény, 7, 1962 pp. 225–226.

V. Chvátal, “Hamiltonian Cycles,” in The Traveling Salesman Problem (E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. Shmoys, eds.), New York: Wiley, 1985 pp. 403–430.

V. Chvátal, “On Hamilton’s Ideals,” Journal of Combinatorial Theory B, 12(2), 1972 pp. 163–168. doi:10.1016/0095-8956(72)90020-2.

V. Chvátal and P. Erdős, “A Note on Hamiltonian Circuits,” Discrete Mathematics, 2(2), 1972 pp. 111–113. doi:10.1016/0012-365X(72)90079-9.

L. Pósa, “On the Circuits of Finite Graphs,” Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közlemény, 8, 1963 pp. 355–361.

D. Angluin and L. G. Valiant, “Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings,” Journal of Computer and System Sciences, 18, 1979 pp. 155–193. doi:10.1016/0022-0000(79)90045-X.

L. Pósa, “Hamiltonian Circuits in Random Graphs,” Discrete Mathematics, 14(4), 1976 pp. 359–364. doi:10.1016/0012-365X(76)90068-6.

V. K. Balakrishnan, “Schaum’s Outline of Theory and Problems of Graph Theory,” New York: McGraw-Hill, 1997, pp. 80–82.

P. Erdős and A. Rényi, “On the Evolution of Random Graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 1960 pp. 17–61. www.math-inst.hu/~p_erdos/1960-10.pdf.

Csongor Gy. Csehi is pursuing his B.Sc. in mathematics at the Budapest University of Technology and Economics. His main research interest is Hamiltonian cycles and semirandom graphs, and also the graphicity of the sum of graphic matroids. He has another accepted paper beyond the present one, with coauthors, entitled “On the Rectifiability Condition of a Second-Order Differential Equation in Special Finsler Spaces.”

János Tóth received his M.Sc. in mathematics at the Loránd Eötvös University of Budapest in 1971 and his Ph.D. from the Hungarian Academy of Sciences in 1986. Currently he is associate professor at the Department of Analysis of the Technical University of Budapest, Hungary, and participates in teaching at Loránd Eötvös University as well. He is the author of Mathematical Models of Chemical Reactions (with P. Érdi), Mathematics and Mathematica (with L. Szili, in Hungarian), Research and Publication in Science (with P. Csermely, T. Koltay, and P. Gergely, in Hungarian), and Differential Equations. An Introduction to the Theory with Applications (with P. L. Simon, in Hungarian).