ComBINATORICA 7 (4) (1987) 327—341 AN ALGORITHM FOR FINDING HAMILTON PATHS AND CYCLES IN RANDOM GRAPHS B. BOLLOBAS, T. I. FENNER and A. M. FRIEZE Received 1 August 1985 Revised 19 September 1986 This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the exis- tence of such a cycle. If all graphs with 7 vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, as 7 tends to ©. Various modifications of HAM are shown to solve several Hamilton path problems. 1, Introduction We shall give a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. As one would expect this algirthm is not perfectly reli- able, ie. a graph G may have a Hamilton cycle but our algorithm may fail to find one. However, if G is chosen at random then our algorithm has an asymptotically small probability of faliure. To be precise: let My denote the set of graphs wih vertex set ¥,={I, 2, ....n} and m edges. We turn [, into a probability space by given each GET, the probability 1 =1 i(*) where N= ()). Let Gy, denote a graph chosen randomly from I’. Now let ap m= nlogn/2+nlog log n/2+¢,n for some sequence ¢,. Komlés and Szemerédi [10] have shown that (0 if q—--3 Jim Pr G,,m i8 hamiltonian) = je" if c~e 1 if g+t< = lim Pr GG,,q has minimum degree at least 2). ‘Supported by NSF Grant MCS 810 4854. AMS subject classification: 05 C 45, 68 E 10.328 8. BOLLOBAS, T. I. FENNER, A. M, FRIEZE Their proof is essentially non-constructive (see also Bollobas [2] or Frieze [7] for alternative non-constructive proofs). Polynomial time algorithms which have a high probability of finding Hamilton cycles have been described by Angluin and Valiant [1] and Shamir [12]. The algorithm due to Shamir [12], HAMI, say, satisfies jim Pr(HAML finds a Hamilton cyle in G,,_) = 1 if c,>(1-+e) log log n for some fixed s>0. We first improve this to obtain the essen- tially best possible result. Theorem 1.1. (a) Let m be defined as in (1.1). Then 0 if ¢~-< lim Pr(HAM finds a Hamilton cycle in G,,,) =je~"" if ¢, + ¢ = 1 if q+ (b) HAM runs in 0(n***) time. (Note that result (a) cannot be improved, although (b) possibly could.) We note that the algorithms described in [1] and [12] require the input graph to have its adjacency lists given in a random order. In our algorithm this is not nec- essary. ‘Thus the previous algorithms can be viewed as randomised algorithms that work well on random inputs while our algorithm is a deterministic algorithm that works well on random inputs. We next consider the case where each of the 2" graphs with vertices V, is equally likely to be chosen. Under this model the probability of failure is so small that, if we apply dynamic programming [9] when HAM fails, we obtain the following result as a corollary of the proof of Theorem 1.1. ‘Theorem 1.2. There is an algorithm for solving the Hamilton cycle problem with polyno- mial expected running time. Our algorithm also has an application in solving the symmetric bottleneck travelling salesman problem (B1 SP). An instance of B1SP is specified by the assign- ment of a numerical weight to the edges of a complete graph K, on 7 vertices. The objective is to find a hamiltonian circuit for which the maximum edge-weight is minimised, Let us assume that edge-weights are drawn independently from the uniform distribution over [0, 1]. Karp and Steele [11] remark that Shamir’s algorithm can be used to find a near optimal solution with probability tending to 1. (Throughout this paper all limits are taken as noo and this is implied if it is not explicitly stated). A modification of our proof of Theorem 1.1 gives Theorem 1.3. There is a polynomial time algorithn BOT satisfying Jim Pr BOT solves BTSP exactly) = 1. We shall also consider the use of HAM is finding hamilton paths. There are 3 cases to consider: (1) find a Hamilton path from vertex 1 to vertex n, (2) find a Hamilton path from vertex 1 to any other vertex, (3) find a Hamilton path without specifying either endpoint.HAMILTON CYCLES 329 Let a Hamilton path satisfying the condition (i), i=1,2,3, be of type i. Then we can construct simple modifications HAMPi to HAM, i=1, 2,3, such that the following result holds. Theorem 1.4. Let m be defined as in (1.1). Then Jim Pr(HAMPi finds a Hamilton path of type i in G,,,) = jim Pr (G,,», Contains a Hamilton path of type i) = = lim Pr (G,,» contains = i—1 vertices of degree 1) = (0 if c+ =feAUtat...429) if cre where 2=en% 1 if qt. We can also use the algorithm to find Hamilton paths between all pairs of vertices. A graph is said to be Hamilton connected if it contains a Hamilton path joining each distinct pair of vertices. Theorem 1.5. Let m= n log n/2+n log logn+c,n. Then lim Pr(G,,m is Hamilton connected) = lim Pr(G,,, has minimum degree at least 3) = 0 if ¢+—e =je-* if c,+c, where 2=e-% 1 if gate. 2. Algorithm HAM lea has been used by many authors: given a path P=(o,, va» sy) plus an edge e={v,, v;} where 1=i=k—2, we can create another path of length k—1 by deleting edge {v;, v;,1} and adding e. ‘Thus let ROTATE (P, €) = (15 025 004 Dis Uks Upnas vos Orta)» ‘The algorithm we describe is based on ideas in the proof used in [6]. It pro- ceeds by a sequence of stages. At the beginning of the k'* stage we have a path Py of length k, with endpoints w, and w,. We try to extend P, from either wo or w,. If we fail but {1, w,}€£ then connectivity tells us that we can find a longer path. Failing this, we do a sequence of rotations which creates new paths that we can try to extend or close. We apply the same construction to all these paths and so on until either we have succeeded in obtaining a path of length k+1 or we have exceeded a certain length of rotation sequence. We now give a formal description: 2330 B. BOLLOBAS, T. I. FENNER, A. M, FRIEZE Algorithm HAM Input: a connected graph G=(V,, £) of minimum degree at least 2. begin let P be the path (1, w) where w=min {v: {1, »}€Z}; k=l LI begin {stage k begins here} =P, sr]; t:=1; 6(Q,):=0; Remark: 5(Q,) is the number of rotations in the sequence constructing Q, from , repeat let path Q, have endpoints wo,w, where wo Pr (G,,phas A;) = ( ) = (" k °) eh ore) (np ntp? + np*+p) S n’pte 7, For p=2logn/n we can use (3.3) and (3.6). For smaller p in the range log n/n=p=2 log n/n we need a bit more work. It follows from (3.2) that there exists m’, m—(n log? n)!2Sm’sm such that Pr (G,,_, has A,)=3n°pte-, Now G,,» is obtained from G,,,, by adding m—m’ random edges. Thus Pr (Gp.m has Ay) Pr (Gym has A,)+7, Pr(G,,, does not have A,) where m= =Pr (one of the m—m’ added edges meets a vertex that is within distance 1 of a small vertex). That 7, is o(1) follows from (a) and m—m’=(n log? n)¥?. (©) PrG,,, has a vertex of degree=5d)=n(41 p= n(e/5)™. Now use (3.3). (d) We prove the result for G=G,,,, the result for G,,» follows from (3.3). For a set KEY, let Ag be the event that” [N(K, G)|=elK|d, where a= 1/300. We first consider |K| large. Suppose first that n'=k=|K|=n/d. We prove a stronger result than needed. Now Pr (there exists K, |K| =k, and A,) = 24-()807aa-nrHAMILTON CYCLES 333 where p,=(1—(1—p)*)=kp=1 is the probability that a vertex not in K is adjacent to at least one vertex of K, if |K|=k. For large n, akd=(n—k)p,/2 and so for some constant ¢>0 Axe () (xt) pitt — pyr k-ak) = = c(ne/k)*(ne/akd)™ (kp) exp (—kd+k-+akd) = 3 o((ne*/k) (e/a)4e~ 4) = =O(n-’) for any constant y > 0, provided n°!=k=n/d. For 1=k=min (n®, n/d) we use two methods of proof which cover the range of possibilties. We first assume that p=O(n~°7*). If there exists a set K ot large vertices such that Ax occurs then, by considering T=KUN(K, G), there exists aset T, |T|=1, d/20S1=n(1+ad) which contains at least 21 edges. Then for some constant c>O Pr(there exist such aT) = ¢ 5 (") (37) p(l—pytn-* = ; = S (ne*ip*/16) = = O(n?) for any constant 7 > 0. We finally consider p=n-°*, We independently orient the edges of G ran- domly to obtain a digraph G’, ie. if {u, o}€£,,, then we direct from w to v with probability 1/2 and from v to w with probability 1/2. Let B be the event ’there exists v€¥, such that vis large in G but has outdegree =d/50 in G’. Since d=n"* we find Pr(B)=O(n-*) for any constant y>0. Suppose then that B does not occur and Ax occurs for some small set K of large vertices. Then there exists a set K all of whose vertices have outdegree =d/50 in G’ for which the outdegree of the set K is no more than a|K|d. Then if k=|K| Pr (there exists such a K) = (i) (0 ) (3) cop2yt*\ = =O(n7) for any constant y >0. Let F,=({GeIy: G is connected, has minimum degree at least 2 and satis- fies all the conditions listed in Lemma 3.1}. Suppose that HAM terminates unsuc- cessfully in stage k on G,,,. Now let YCE be deletable if: (i) no edge of X meets a small vertex; (ii) no large vertex meets more than d/1000 edges of X; Gii) XAW@=9. Lemma 3.2. Suppose HAM terminates unsuccessfully in stage k on G=Gy.m€T 1. Suppose XCE is deletable. Then for, n large, (3.6) JEND (G,)| = n/1000; G2 |END (Gx, x)| = n/1000 for x¢END(G,).334 B. BOLLOBAS, T. I. FENNER, A. M. FRIEZE Proof. Consider the execution of HAM on Gy. From Lemma 2.1 we know that HAM will start stage k with the same P, as for G and terminate unsuccessfully in this stage. Suppose P, has endpoints w, and w,. Let S,={v: v is large (in G) and there exists a path Q, with endpoints wo, v such that 5(Q,)=1}. We prove (3.6) by showing that (3.8) | 0 'S,| = n/1000. Pat We show first that, for n large, Sy#0. Let x9, 1, ...,%, be the neighbours of wy, in Gx where {xp, w,} is an edge of P,=Q,. Let y, be the endpoint, other than Wo, Of ROTATE (P;, fw, w)) for i=, 2,...,h. Case 1: wy is small. Then h=1 as GF, and X is deletable. Also y, is large (Lemma 3.1(b)) and so y,€S}. Case 2: w, is large. h=d/20—d/1000—1 for n large. Also at most one of y1, Yes -- Yn can be small (Lemma 3.1(b)) and so |S,|=h—1>0 for n large. We show next that, for 7 large, (3.9) [S| = nfd implies |S,,:| = d|S,|/1000. For each vertex v€S, choose one path Ox.) with endpoints wy and v such that 5(Qy)=t. Consider now pairs (v, w) where véS, and weW(v)=N(fo}, Gy). If {o, w} is not an edge of Oy.) let x(v, w) be the endpoint of ROTATE (Qy. {v, w}) other than w. If x(v, w) is large then x€S,41. Let (@) {vw} is an edge of Oxy OR 1 if (b) x =x(v, w) is small OR (Cc) {x, w} is not an edge of P,. 0 otherwise Now for each v€S, there are at most t+2 w’s such that a(v, w)=1 (1 for ech of (a) and (b) and t for (c) as Qyw) is obtained from P, by # rotations and hence contains at most f edges not in P,). On the other hand, for each w€N(S,, Gx) there can be at most 2.x€S,,, such that for some v€S,, x=x(v,w) and a(v, w)=0, since x will be a neighbour of w on P,. Thus IS.+11 = [{x(0, w): v€S,, wEW(v) and x(0, w) is large)| = = [{x(v, w): véS,, weW() and a(v, w) = 0}| = = I{we M(S,, Gx): there exists v€S, with a(v, w) = 0}|/2 = = (IM(S,, Gx) -C+2)1S)/2 = = (IN(S,, | —(4/1000-+4+2)|S,))/2 = = (d/300—(d/1000+7 +2))|S,/2 = =d|S\/999 for n large. a(e, w) =HAMILTON CYCLES 335 Since $,#0 and (3.9) holds, we know that for some t=T—1 that |S,|=n/d. Let S’SS, be of size [n/d]. Applying the same argument as used to prove (3.9), using S” in place of S, we have |S,+1|=d|S’|/999=n/1000 for n large. This verifies (3.6). To prove (3.7) consider x€END (Gx), choose a path Q=Q, having x as one of its endpoints and 6(Q,)=7 and then redefine $,= {v: v is large (in G) and there exists a path Q, with endpoints x, v such that Q, is obtained from Q, using t rotations with x as a fixed endpoint}. Now apply the argument used to prove (3.9), using Q, in place of P,, to prove (3.7). ‘We can now prove Theorem 1.1. Now it is known (see for example Erdés and Rényi [5]) that if c,+»—< then Gy,» is a.s. connected and in general Pr(G,, has a vertex of degree 1) ~ 1—e-¢7**", Thus if ¢,+—=, G,,m a.s. has a vertex of degree 1 and so there is nothing to prove. If cyt»—e> then, using Lemma 3.1, we have 3.10) IN| = (1-o())e“e**" Fl. Now let [,={G: Ge, and HAM terminates unsuccessfully on G}. It follows from (3.10) that to prove Theorem 1.1. we need only show that G.I) Aim |P,\/ITo| = 0. To prove (3.11) we use a colouring argument developed in Fenner and Frieze [6]. Let now w=[Ad] for some constant 4>0. For each GEM, let (G,/), /=1, 2, 5 7=(%") enumerate all the possible ways of colouring w edges of G green and the remaining m—w edges blue. Let Y=X(G,j) denote the set of green edges. Let 1 if (3.12a) HAM terminates unsuccessfully on G and Gx; (3.12b) there does not exist e = {x, »}€X such that x€END (Gx) and y€END (x); (3.12c) |END (G,)| = 1/1000 and |END (Gy, x)| = 7/1000 for all x€END (Gy) a(G,j)= 0 otherwise. We show first that for Gel, Z F my) G13) SalG.j= (1-0 (") where m, = m—(QT+2)n =(1—o(1))m. ran To see this let GET, and let HAM terminate unsuccessfully in stage k on G. As GET;, it follows from (2.1), Lemma 2.1 and Lemma 3.2 that if ¥=X(G,/) is deletable then a(G,/)=1. Let G’=(V’, E’) be the subgraph of G induced by the large vertices and those edges not in W(G). Then (V’)=n—n¥? and |E’|= =m'=m—n(2T +2). The number of deletable sets is the number of ways of choosing w edges from E’ subject to the condition that no vertex in V’ has more than d/1000336 B. BOLLOBAS, T. I. FENNER, A. M. FRIEZE of its incident vertices chosen. Using Lemma 3.1(c) it is not difficult to show that this is (1-0(1)) ) which implies (3.13). (Choose edges of £’ independently with prob- ability 42/n. One almost surely chooses more than w edges. Furthermore the number of edges chosen incident with a given vertex is dominated stochastically by a binomial random variable with parameters [Sd| and 42/n). On the other hand, let H be a fixed graph with vertices V, and m—w edges. Let b(H)=I{(G,j): H=Gy, GET) and aG,j)=1}|. We see that (3.14) oan =(" rt") where w=()-('2"). If (3.12a) or (3.12b) do not hold for H (replace Gy by H in these statements) then by=0. Given (3.12a), (3.12b) there are at most N’—m-+w edges to choose from in order to unsure (3.12c). Now X XaG,j)= Fo). Thus oto " o-oo (Rins= 2 Zan wy o19 =X SaGn= aA = ous = (re) (nw) by G.14) Thus e159 tratira = (roy (8 "| (D/A) (Ms = (1+0(1))((N’—m+w)(m—w))/(N—m+w)(m, —w))" = = (1+0(1))e-%-¥9¥ (1+ 0(1))" = = en 4/to01 for m large, ‘We can take any constant value 4>0 here and this will complete the proof of Theorem 1.1(a). To prove part (b) we note that on GP, HAM executes O(n(d)*")=O(%3**) rotations. Thus, as given, HAM runs in time O(n'**) with probability 1—o0(1). We can easily make it run in time O(n‘**) by imposinga suitable time limit. ‘We now turn to the proof of Theorem 1.2. If all graphs are equally likely to be chosen then this is the same model as G,,,, p= 1/2. We use (3.2) where property A will mean that the given graph is connected, has minimum degree at least 2 andHAMILTON CYCLES 337 yet HAM terminates unsuccessfully. We will show that (3.16) Pr(Gy,1j2 has A) = 0(1/2"). Since Dynamic Programming requires time O(n?2"), this will prove the theo- rem. Using Theorem J. 7(i) of [3], for the tail of the Binomial Distribution we see that G.17) Pr (\[Eq,1/21—7°/4| = (a? log n)"*) = 0(1/3"). Thus, using (3.2), we need only prove (3.18) Pr (Gy,m has A) = 0(1/2") for |m’—n*/4] <(n® log n)"*, Letting I, 0, 1,2 refer to G,,m we define I'j={GEIy: G does not sa- tisfy all the conditions of Lemma 3.1} and I'4={G€I'y: G is connected, has mini- mum degree at least 2 and yet HAM terminates unsuccessfully on G}. ‘Then Pr(Gpyy has AY=(P4l/\Pol SIMI ol + Wa Talo = (aM ol + [Pal/IPol. Now | let d’=2m'/n=(1—o(1))n/2_ in our range of interest. We see that, for large n, conditions (b) and (d) of Lemma 3.1 are always true for G,,»-. It follows from (3.3), (3.5) and (3.6) that [I4|/\Pol=Pr Gy, I'1)= O(n exp (—n*/8/25)+n° exp (—0,74n))= =0(1/2"). Putting 2=2000002 in (3.15) shows that |I’,|/|'o|=o(e~") and this completes the proof of Theorem 1.2. 4, Algorithm BOT ‘We turn now to BTSP. Given an instance of this problem, let the edges of K, be ordered ¢;,€2, ....ey where c(e,)Sc(e,)5...SC(ey), c(e) being the ‘cost” of edge e, Let E,={e;, €2, ...,e} and let G.=(%, E,). Note that G, has the same distribution as G,,.- Algorithm BOT begin Iet_ w=min {¢: G, has minimum degree at least 2}; apply HAM to G, end It is clear that if HAM terminates successfully on G, then BOT solves BTSP exactly. We cannot apply Theorem 1.1. directly as G,, as defined in BOT above has a slightly different distribution to G,,, conditional on minimum degree 2. Let_m’= =|[n log n/2-+n log log n/2—n log log n/2| and m”=m'+[nlog loglog ni]. It is known that G,, a.s. is connected and has minimum degree 1 and that Gy a.s. has minimum degree 2. Thus m’= 0. me (Although Lemma 3.1 specifically excludes ¢,+—0, using (3.13) and (3.10). By choosing 2=2000002 we obtain aD Z,Pr(Cul Ba) = o(l) ‘Theorem 1.3 now follows from (4.1), (4.6) and (4.7).HAMILTON CYCLES 339 5. Hamilton Paths We shall view the problem of finding a Hamilton path from vertex a to vertex b in a graph G as that of finding a Hamilton cycle in the graph G(a, )= (VG), E(G)Uf{a, b}}) that contains the edge {a, b}. To ensure that HAM searches for a Hamilton cycle containing a particular edge {a, b} we make some minor modifica~ tions: (1) Initialisation Let G=G,,n(a, 6). Let Hy be the graph induced by the edge {a, b} and all edges incident with vertices of degree 2 in G. If Hy contains a cycle or a vertex of degree 3 or more then HAM terminates successfully (success means that HAM has been able to decide as to whether or not G contains a Hamilton cycle using the edge {a, b}). Otherwise, if H, consists of vertex disjoint paths, then we say that the degree 2 vertices of G,, are compatible with {a, b}. In this case we initialise P, to be the component of H, containing {a, b}. (2) Rotations We omit any rotation that involves deleting an edge of Py. (3) Cycle Extensions If HAM wishes to do a cycle extension but can only do so by deleting an edge of P, then HAM will terminate unsuccessfully, otherwise HAM will choose the “first” possible ‘legal’ cycle extension. Note that HAM will not terminate unsuccess- fully in (3) if (5.1) G,,» does not contain a path P of length 3 or more which has at most 2 vertices which have neighbours not in P. We call HAM with the above modifications HAM (a, b). Next let (a, b)={Gy,m: (1) Gym satisfies all the conditions of Lemma 3.1 as well as (5.1), (2) G,,(a, 6) has minimum degree at least 2}. Note that it is straight- forward to show that Gy,» a.s. satisfies (5.1). We next indicate the proof of Lemma 5.1. Pr(HAM (1,7) terminates unsuccessfully |G,,,€Ty(1, 0))=O(™) for any constant y>0. Proof. (Outline) The proof of Lemma 3.2 requires only small modifications. Consider first the proof that 5,40. Only Case 1 requires a mention. If Pj~(1,n) then by condition (b) of Lemma 3.1 all neighbours of w; yield legal rotations. If P,=(1,n) there is only a problem if w, is of degree 2 and 1 or nis a neighbour of w;. But then we have the contraction that 1, is a vertex of P, or 1, n are both neighbours of wy. For the rest of the proof of Lemma 3.2 the only change is that t+-2 is replaced by 143. The colouring argument that follows Lemma 3.2 goes through with only trivial changes, particularly if we separate the cases {1,n}¢EG,,») and {1, M}EEGz,m)- Since A can be chosen arbitrarily large in this argument, we have the stated O(n-*) probability of failure. Theorem 1.4 and 1.5 are consequences of340 B, BOLLOBAS, T. I. FENNER, A. M. FRIEZE Lemma 5.2. Let m=(n log n-+n log log n)/2+c,n where ¢,=—O(I). For 1=i=jsn let A(i,j) denote the event that G=G,, ,(i,j) has minimum degree at least 2, the degree 2 vertices of G,,™ are compatible with {i, j} and yet HAM (i, j) fails to find a Hamilton cycle in G using {i,j}. Let a 4-9 0 aan Then Jim Pr(A) = 0. Proof. Pr (A)=Pr (A and G,,, satisfies the conditions of Lemma 3.1 and (5.1))+ mon +0()=Pr(U OU (GamETi(i,j) and HAM terminates unsuccessfully) + it joie +o(I)= () Pr(HAM (1, n) terminates unsuccessfully |G, .€I(1, »))-+0(1)=0(1). Theorem 1.5 follows immediately. ‘Theorem 1.4(1) follows from the fact that vertices 1 and m are a.s. large, and have no degree 2 neighbours. ‘Theorem 1.4(2) and (3) follows from the above and the fact that a.s. no vertex of degree 1 has a degree 2 neighbour. 6. Conclusions ‘The results of this paper show that the hamiltonian cycle problem can be con- sidered to be well-solved in a prohabilistic sense. They can be extended to cover the problem of finding disjoint hamiltonian cycles by following the approach described in Bollobaés and Frieze [4]. Indeed all one has to do is to repeatedly apply HAM and remove Hamilton cycles. The proof that this works with the same limiting probability as that of having minimum degree 2k can be obtained from the proof of Theorem 1.1 with only slight modifications. With a few minor changes to the proofs one can show that HAM combined with Dynamic Programming has polynomial expected running time for G,,» if p>1—1/V2. For smaller p we find that the probability that there are 2 vertices of degree 2 which are close exceeds (1/2+e)". However, by initially covering vertices of small degree with vertex disjoint paths, if possible, we can obtain a polynominal expected running time algorithm whenever p is a positive constant. Independently, Gurevich and Shelah [8] have constructed an O(n) expected running time Hamilton path algorithm for p constant. Subsequently, a similar result has been obtained by ‘Thomason [13]. In a future note we hope to show that HAM combined with Dynamic Programming has O(n) expected running time for G,,, if p>1—1/)2.HAMILTON CYCLES 341 References [1] D. Axotum and L. G. Vatian, Fast probabilistic algorithms for Hamilton circuits and mate- chings, J. Computer Syst. 18, (1979), 155—193. [2] B. BoLLosés, Almost all regular graphs are Hamiltonian, European Journal of Combinatories 4, (1983), 311—316. [3] B. BottopAs, Random Graphs, Academic Press, London, (1985). [4] B. Bottosés and A. M. Frirzt, On matchings and Hamilton cycles in random graphs, Annals of Discrete Mathematics, 28 (1985), 23—46. [5] P. Expés and A. RENY1, On the strength of connectedness of a random graph. Acta. Math. Acad. Sei. Hungar. 12, (1961), 261—267. [6] T. 1. Fenner and A. M. Frieze, On the existence of Hamilton cycles in a class of random graphs. Discrete Mathematics 45, (1983), 301—305. 17] A. M. Frieze, Limit distribution for the existence of Hamiltonian cycles in arandom bipartite graph, European Journal of Combinatorics, 6 (1985), 327334. [8] Y. Gurevich and S. SHetax, Technical Report of the University of Michigan, 1985. [9] M. Het and R. M. Karp, A dynamic programming approach to sequencing problems, SIAM Journal on Applied Mathematics 10, (1962), 196—210. [10] M. Komios and E. Szemeréot, Limit distribution for the existence of a Hamilton cycle in a random graph, Discrete Mathematics 43, (1983), 55—63. [11] R. M. Kare and J. M. Sreeze, Probabilistic analysis of the travelling salesman problem, in The Travelling Salesman Problem: A Guided Tour (E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy-Kan and D. B. Shmoys, eds), John Wiley and Sons (1985). [12] E. Suamin, How many edges are needed to make a random graph Hamiltonian? Combinatorica 3, (1983), 123132. [13] A. G. Thomason, A simple linear expected time algorithm for Hamilton cycles, to appear. B. Bollobas T. I. Fenner Department of Pure Mathematics Department of Computer Science University of Cambridge, Cabridge, England Birkbeck College, University of London, England Department of Mathematics LSU, Baton Rouge, LA, USA A. M. Frieze Department of Computer Science ‘Queen Mary College, University of London, England Department of Mathematics Carnegie Mellon University, Pittsburgh, PA, USA.