A Distributed algorithm to find Hamiltonian cycles in Gnp random graphs

A distributed algorithm to find Hamiltonian cycles in G(n, p)random graphs∗ Eythan Levy†Guy Louchard†Jordi Petit‡ Abstract In this paper, we present a distributed algorithm to find Hamiltonian cycles in random binomial graphs G(n, pn). The algorithm works on a synchronous distributed setting by first creating a small cycle, then covering almost all vertices in the graph with several disjoint paths, and finally patching these paths and the uncovered vertices to the cycle. Our analysis shows that, with high probability, our algorithm is able to find a Hamiltonian cycle in G(n, pn) when pn=ω(√log n/n1/4). Moreover, we conduct an average case complexity analysis that shows that our algorithm terminates in expected sub-linear time, namely in O(n3/4+²) pulses. 1 Introduction It is well known that finding a Hamiltonian cycle in a graph is an NP-hard problem [6]. Therefore, a possible way to cope with this problem is to devise algorithms that are fast on the average with respect to a natural probability distribution of graphs. The main purpose of this paper is to present and analyze a randomized distributed algorithm to find Hamiltonian cycles in binomial random graphs. Recall that a Hamiltonian cycle is a cycle that visits each vertex of a graph exactly once. If a graph has a Hamiltonian cycle, it is said to be Hamiltonian. The model of random graphs that we consider is the popular G(n, pn) binomial random graph distribution. In this model, graphs contain nvertices {1,...,n}and each of the ¡n 2¢possible edges are independently included with probability pn. The question whether a binomial random graph is Hamiltonian is well solved: For any divergent function t(n), a graph in G(n, pn) is Hamiltonian with high probability for pn= (log n+ log log n+t(n))/n; see [2] for a classical reference. Several algorithms have been proposed to deliver, with high probability, Hamiltonian cycles in G(n, pn) graphs provided that pnis sufficiently large. Recall that a sequence of events (En)n∈Nholds with high probability (w.h.p.) if limn→∞ Pr[En] = 1. Angluin and ∗This research was partially supported by the IST Programme of the EU under contract number IST1999-14186 (ALCOM-FT) and by the Spanish CICYT project TIC2002-04498-C05-03 (TRACER). †D´epartement d’Informatique, Universit´e Libre de Bruxelles. Bld du Triomphe — CP 212, B-1050 Bruxelles (Belgium). {elevy, louchard}@ulb.ac.be ‡Departament de Llenguatges i Sistemes Inform`atics, Universitat Polit`ecnica de Catalunya. Campus Nord C6-207. 08034 Barcelona (Spain). jp[email protected]c.es 1 Valiant [1] devised an O(nlog2n) algorithm to find Hamiltonian cycles w.h.p when pnis high enough. Later, Shamir [13] improved this algorithm to cope with lower probabilities of the form pn≥c(log n+ log log n)/n with c > 3. Gurevich and Shelah [7] presented a linear time algorithm when pnis constant. The HAM algorithm of Bollob´as, Fenner and Frieze [3] runs in expected polynomial time and is essentially best possible with regards to pn. On the other hand, it has also been shown that there exist exact algorithms to determine whether or not a graph is Hamiltonian that run in polynomial expected running time over the class of binomial random graphs: Bollob´as, Fenner and Frieze [3] also gave an algorithm to decide Hamiltonicity in G(n, p) graphs with p≥1/2 in expected polynomial time. Thomason [15] improved this result to expected O(n/pn) time when pn≥12n−1/3. Also, Frieze [5] presented a parallel algorithm that for any constant pdecides Hamiltonicity in expected poly-logarithmic time on a PRAM. As said, all these algorithms are sequential, except Frieze’s parallel algorithm for PRAM machines (with a centralized memory). However, to the best of our knowledge, a fully distributed algorithm for this problem has not been yet proposed. Such an algorithm could nevertheless find interesting applications in the fields of distributed computation. For instance, with a Hamiltonian cycle it is possible to build a path to perform distributed computations based on end-to-end communication protocols, which allow distributed algorithms to treat an unreliable network as a reliable channel [12]. Also, a Hamiltonian cycle is useful for the purpose of forming token rings in the network, establishing a sense of direction, and as part of distributed algorithms for election or mutual exclusion [11, 14]. Our algorithm can also find useful applications in emerging systems, as we will discuss in the conclusions. Our setting for distributed computation is the classical model of synchronous networks (see e.g. Chapter 12 in [14]), where the algorithm takes place in a sequence of discrete steps, called pulses,in which every process first sends (zero or more) messages, then receives all the messages addressed to it during that same pulse, and finally performs local computations. Our distributed algorithm is designed for random graphs in the sense that the topology of the network is obtained by selecting a random graph, which means that each node of the network corresponds to a vertex of the graph. As usual, a node can only communicate with its direct neighbors in the graph and has no direct knowledge of the rest of the network topology. Finally, we suppose that the nodes are labeled in a way consistent with that of the G(n, pn) graph, and that nodes know the identities of their neighbors. Recall that the time complexity of distributed synchronous algorithms is defined as the number of pulses needed for the algorithm to terminate. Our algorithm has been designed to optimize time complexity, rather than message complexity. It is a well known fact in distributed computation that the optimization of these two quantities are often conflicting goals. Within this setting, the paper is organized as follows: First, we present a high level description of the distributed algorithm. Then, we analyze it’s probability of success over the probability space of G(n, pn) graphs for a suitable probability function pn. Our results show that w.h.p. our algorithm finds Hamiltonian cycles when pn=ω(√log n/n1/4). Finally, we prove that the average running complexity of our algorithm is O(n3/4+²) pulses. We close the paper with some concluding remarks. Due to lack of space, we omit a formal exposition of the algorithm and simply sketch most of the proofs. Complete proofs will be included in the full version of this paper and can be obtained at [10]. 2 (a) End of phase 1 (b) End of phase 2 (c) Phase 3 in process (d) End of Phase 3 Figure 1: Phases of the algorithm. 2 High level description of the algorithm Our algorithm works in three main sequential phases: 1. Initial cycle phase: In this phase an initial small cycle with Θ(√n) vertices is found in the graph. 2. Path covering phase: In this phase, almost all the vertices out of the initial cycle are covered by √nvertex-disjoint paths. 3. Patching phase: In this phase, each path and each non covered vertex is patched into the initial cycle. Let us give some more details on each phase. Figure 1 depicts the phases of the algorithm. Phase 1 (Initial cycle). The goal of this phase is to build an initial cycle of length Θ(√n). In order to build such a cycle, the algorithm proceeds in two steps. First, it sequentially builds a path of length λ1= 6√nbeginning with a initiator vertex (which we call v0); then, it tries to loop this path back to v0by extending the path as long as the path extremity is not adjacent to v0. The algorithm stops its execution with a failure —and broadcasts the failure information to all nodes— if the length of the path becomes greater than λ2= 7√nor if it does not succeed in extending the path. Broadcasting in a graph of arbitrary topology can be done in linear worst-case time with respect to the diameter using a wave algorithm (see Chapter 6 of [14]). 3 Vertices in the cycle (and in the paths of Phase 2) are said to be “used” and vertices out of the cycle are said to be “free”. At all times the nodes should know the subset of their neighbors that are still free. To achieve this, the new endpoint of the current path always sends a message to all its (free) neighbors, notifying them of its transition to the “used” state. Phase 2 (Path covering). The goal of this phase is to cover almost all the vertices not included in the cycle by a set of √nvertex-disjoint paths leaving, at most, √nvertices uncovered. In order to cover the vertices, the √npaths will grow in parallel from a set of √ninitial vertices chosen by v0among its free neighbors, after the completion of the initial cycle. A path extends its-self by its two extremities in the following way: an extremity chooses one of its free neighbors uniformly at random, and sends an extension message to it, waiting for its answer. These choices are synchronized between all the participating extremities. Free vertices wait for extension messages emanating from the extremities and pick one of these messages uniformly at random, to which they answer. Then, each one of these free neighbors thus becomes the new extremity of one of the paths, and will execute this same extension mechanism at the next round of Phase 2. All path extremities that have not received an answer from the free neighbor they had chosen are not allowed to participate to the following rounds of Phase 2; their extension is then completely stopped. The absence of free neighbors is another possible reason for the ceasing of the extension at one extremity. When a path extremity cannot extend itself anymore, it sends its identity, together with the length of its (half-)path, to the initiator. The initiator is always reachable by transmitting the message through the path itself, toward the initial node of that path. After v0has received these termination messages from all the √ncovering paths, it is able to determine if the covering phase is successful or not. In the negative case, that is, when more than √nvertices have remained uncovered, the initiator terminates the algorithm with failure, by broadcasting the failure information to all nodes. In this phase, we also suppose that, in the same way as in Phase 1, the newly selected path extremities begin by sending a message to all their (free) neighbors, notifying them of their new used state. Phase 3 (Patching). In this phase, the paths and the uncovered vertices are tried to be patched to the initial cycle. In the case that all of all them can be patched to the cycle, a Hamiltonian cycle will be returned; otherwise the algorithm will report failure. In the following, uncovered vertices will be treated as paths of length zero. Phase 3 starts by gathering in v0the identities of the uncovered vertices. This can easily be done using a wave algorithm as shown in [14]. Patching an individual path to the cycle is done according to the simple idea depicted in Figure 2: if uand vare two consecutive vertices in the cycle and sand tare the two endpoints of the path, the path can be patched to the cycle if edges us and vt or ut and vs exist in the graph. Patching a path with length zero to a cycle is done in the same way, just taking s=t. In practice, the patching trials, for a fixed path, are done using a patching message that circulates round the cycle, and contains the identities of sand to t, as well as two boolean variables denoting whether the sender of the message is adjacent to sand t. Let C1,...,Ck, with C1=v0, be the nodes of the cycle. The message is initially launched by v0, and upon 4 arrival at a node Ck, checks whether the path is patchable to nodes Ck−1and Ck. If it is the case, then nodes s,t, and Ck−1are notified of the cycle update and the patching of the path terminates. If not, the patching message is updated, and sent by Cktowards Ck+1. If the patching message loops back to the initiator with no success, then the patching for that path has failed. The overall patching of the paths is done in parallel, by pipelining several patching messages —one per path— on the cycle. These messages are initially launched by v0, separated by a delay of three time pulses, in order to avoid possible inconsistencies in the patchings performed by two adjacent messages. This delay between the messages explains the constants 6 and 7 used in Phase 1: they guarantee that the cycle is long enough to contain all the patching messages. When a patching trial succeeds, a notifying message is sent towards the initiator, using a broadcast algorithm. Thus, at the end of Phase 3, the initiator knows exactly how many patching trials have succeeded, and performs one last broadcast in order to notify all the nodes of the final result of the algorithm, being success or failure. In the successful case, all nodes have the knowledge of their two neighbors in the Hamiltonian cycle. (a) Cycle and path (b) First possibility (c) Second possibility Figure 2: Patching a path into a cycle. 3 Analysis of the probability of success In this section, we estimate the probability that the proposed algorithm finds a Hamiltonian cycle on a random binomial graph. We work with pn=ω(n−1/4√log n), the reason will be apparent in the proof of Lemma 3.5. Let Ii nbe the indicator random variables denoting the success of Phase iconditioned to the success of Phase j, with j < i. Then, denote by In=I1 n·I2 n·I3 nthe indicator random variables denoting that the algorithm finds a Hamiltonian cycle. We start by showing that Phase 1 succeeds w.h.p. when pn=ω(n−1/4√log n): Lemma 3.1. For all pn=ω(n−1/4√log n), we have Pr[I1 n= 1] →1. Proof. For the sake of making the proof clearer, assume that the first phase of the algorithm has been replaced by the following algorithm, which trivially has a lower probability of success: Instead of computing first a path of length λ1and then trying to close it until it reaches a maximal length λ2, directly build a path of length λ2(Phase 1a) and then try to close the 5 path by successively trying the vertices from λ2to λ1(Phase 1b). We show below that this variant has a high probability of success. Call step ithe step where the algorithm tries to extend a path of length i−1. The probability that phase 1a succeeds is: Pr[I1a n] = Pr[∧λ2 i=1 step isucceeds | ∧j<i step jsucceeds] = λ2 Y i=1 (1 −fn−i n)≥ λ2 Y i=1 (1 −fn−λ2 n) =³1−fn−7√n n´6√n=¡1−fΘ(n) n¢Θ(√n)=¡1−(1 −pn)Θ(n)¢Θ(√n) ∼¡1−e−pnΘ(n)¢Θ(√n)∼³e−e−pnΘ(n)Θ(√n)´. Let us see under which conditions this quantity tends to infinity: ³e−e−pnΘ(n)Θ(√n)´→1⇐⇒ e−pnΘ(n)Θ(√n)→0 ⇐⇒ exp log ¡e−pnΘ(n)Θ(√n)¢→0 ⇐⇒ log ¡e−pnΘ(n)Θ(√n)¢→ −∞ ⇐=−pnΘ(n) + Θ(log n)→ −∞ ⇐=pn=ω(n−1 4plog n). On the other hand, since √nedges are tried for closing the cycle, we have Pr[I1b n= 1] = 1 −fΘ(√n) n, which tends to 1 as ntends to infinity when pn=ω(n−1/2), by the exp-log transformation. As Pr[I1 n= 1] = Pr[I1a n= 1] ·Pr[I1b n= 1], we get the desired result. Let I2a nbe the indicator random variable denoting wether the initiator can find the √n free vertices that will initiate the covering paths in Phase 2. Lemma 3.2. For all pn=ω(n−1/4√log n), we have Pr[I2a n=1]→1. Proof. Note that the number of free neighbors of the initiator is given by a random variable with binomial distribution Bin(Θ(n), pn). The result follows immediately from an application of Chebyshev’s inequality to that variable. Let I2b nbe the indicator random variable denoting wether the extension algorithm succeeds in covering all but at most √nof the free vertices. Lemma 3.3. For all pn= (log n+δ(n))/√nwith δ(n)→ ∞, we have Pr[I2b n= 1] →1. Proof. The probability of being able to cover all but at most √nof the free vertices, using our √ndisjoint paths is bounded below by the probability of attaining such a covering using only one path (unidirectionally). We shall show that the probability of this last event, say π, tends to one as ntends to infinity. Let Fbe the number of free vertices at the start of Phase 2. Note that, at each round of the algorithm, as long as there remains more √nfree nodes, the probability of ceasing the extension phase is bounded above by (1−pn)√n, the probability of the extremity not being adjacent to √nfixed free vertices. 6 Since πequals the probability of being able to extend the path more than F−√ntimes, we have: π≥³1−(1 −pn)√n´F−√n=³1−(1 −pn)√n´n−Θ(√n) >³1−(1 −pn)√n´n∼e−n(1−pn)√n. The last of the above expressions tends to one if and only if n(1 −pn)√ntends to 0, which is the case if and only if pn=log n+δ(n) √n, with δ(n)→ ∞: e−n(1−pn)√n→1⇐⇒ n(1 −pn)√n→0⇐⇒ ne−pn√n→0 ⇐⇒ log ³ne−pn√n´→−∞⇐⇒log n−pn√n→ −∞ ⇐⇒ pn=log n+δ(n) √n, with δ(n)→ ∞. From Lemma 3.2 and Lemma 3.3, we get the probability of success of Phase 2: Lemma 3.4. For all pn=ω(n−1/4√log n), Pr[I2 n=1]→1. We finally compute the probability of success of Phase 3. Lemma 3.5. For all pn=ω(n−1/4√log n), Pr[I3 n=1]→1. Proof. The probability of success of our algorithm is trivially higher than the probability of success of the following variant patching procedure. In the variant algorithm, only one edge out of two, alternatively, is tried for patching, i.e., if the nodes of the cycle are C1,...Ck, only edges C1C2,C3C4,...will be tried for patching. This variant patching algorithm has the advantage of making only independent patching trials. We show below that its probability of success tends to 1. Note that at wathever stage of the patching phase, the length of the initial cycle is always Ω(√n). It is also easy to see that the probability of success of one fixed patching trial of a path at edge CiCi+1 is p2 nif the path has length 0, and 2p2 n−p4 notherwise. It is thus always Θ(p2 n). We can conclude that the probability of failure of our variant algorithm is bounded above by (1 −Θ(p2 n))√n. Since we need to patch Θ(√n) paths, we have: Pr[I3 n= 1] ≥³1−(1 −Θ(p2 n))Θ(√n)´Θ(√n) Using similar techniques as in the previous proofs, it can be shown that the above probability tends to 1. From the preceding results, we obtain that the distributed algorithm finds a Hamiltonian cycle w.h.p.: Theorem 3.6. For all pn=ω(n−1/4√log n), we have limn→∞ Pr[In= 1] = 1. 7 4 Complexity analysis In this section, we analyze the expected running time of the synchronous distributed algorithm. Let Tnbe the random variable denoting the time complexity of our algorithm on a G(n, pn) random graph, with pn=ω(n−1/4√log n). Also, let T1 n,T2 n,T3 nand T4 nbe the random variables denoting respectively, the costs of Phases 1, 2, 3 and of the termination wave. For the sake of simplicity, the waves executed at the end of Phase 3 shall be counted in T4 n. In order to get an upper bound on the average-case complexity of the algorithm, below we analyze the expected complexity of each of these variables. The worst-case time complexity of Phase 1 is easily seen to be Θ(√n), since this phase sequentially establishes a path of length Θ(√n), with the establishment of each edge of the path taking constant time. Therefore, we have: Lemma 4.1. E[T1 n]=O(√n). Let Diam(G) be the expected value of the maximal diameter of the connected components of a graph G. The next result characterizes the expected diameter of G(n, pn) graphs: Lemma 4.2. Let pn=ω(n−1/4√log n). Then E[Diam(G(n, pn))] = Oµlog n pn¶=o³n1/4plog n´ Sketch of the proof. The full proof is omitted here. In short, we bound the diameter of the graph by the height of a random tree inspired by the Galton–Watson process outlined in [8]. We then show the average height of that tree to be O³log n pn´using the saddle point method. The main element for the proof on the running time of Phase 2 is given by the lemma below, whose proof is based on a discrete urns modelization of the path covering algorithm. The complete proof uses tools such as limiting theorems for urns occupations, Brownian motion and differential equations. Lemma 4.3. Let Gbe a G(n, pn) graph, with n=n2 0+n0. Let there be n0initial vertices used to cover the remaining n2 0vertices of Gusing our paths extension algorithm. Let α > 3/4, ² > 0, and pn≥α+² n2α 0ln n0. Let Vαbe defined as the time needed to reach a configuration with less than n2α 0free vertices, if such a configuration is reached, 0 otherwise. Then, E[Vα] = 2n0−nα 0. The following lemma describes the time complexity of Phase 2: Lemma 4.4. For all ² > 0, E[T2 n] = O(n3/4+²). Sketch of the proof. Observe that pn≥(α+²)(n2α 0) ln(n0) because pn=ω(n−1/4√log n). From Lemma 4.3, it is easy to conclude that, under the hypotheses of that lemma, the average time necessary for the extension algorithm to terminate is O(n2α 0). This comes from the following observation: starting from a configuration with less than n2α 0free vertices, the worst-case complexity is O(n2α 0), since the worst-case occurs when only one vertex is covered 8 during each slot. Our upper bound of O(n2α 0) on the average time complexity is simply the sum of the average time needed given by lemma 4.3 and the worst-case bound given above. This result concerns the hypotheses of Lemma 4.3. We find ourselves however in a case very similar to that of Lemma 4.3: we want to end up with less than nαfree vertices, starting from a configuration with √ninitial path vertices and n−Θ(√n) initial free vertices, whereas in the above lemma, we wanted to end up with less than n2α 0free vertices, starting with n0initial path vertices and n2 0initial free vertices. The only difference with the case of Lemma 4.3 above is thus that we have here fewer initially free vertices (n−Θ(√n) instead of n). It is nevertheless easy to see that the time complexity of the extension algorithm is lower when less vertices need to be covered, from which we conclude that the bound of O(n2α 0)=O(nα) = O(n3/4+²) still holds. Finally, E[Diam(G(n, pn))] must be added to the complexity, because of the wave algorithm launched by the initiator at the end of phase is linear with diameter of the connected component. The former term, however, dominates this time, which, by Lemma 4.2, is o¡n1/4√log n¢. In order to analyze Phase 3, we first compute a bound on the cost of patching a fixed path to the cycle. Afterward, we shall compute a bound on the total cost of the parallel patching of all paths. Lemma 4.5. Let TPbe the random variable that denotes the time necessary to patch a path or a vertex to a cycle of any length by our algorithm. Then, E[TP] = O(1/p2 n). Sketch of the proof. Let C1, C2,...,Clbe the vertices in the cycle. It is easy to see that the probability of success of one patching trial is p2 nfor a vertex and 2p2 n−p4 nfor a path. The probability of success being lower for a vertex, it is clear that the average complexity of the patching of a vertex is an upper bound for the average complexity of the patching of a path. We further bound the time complexity for the patching of a vertex by our algorithm by the time complexity of the following algorithm: Perform alternate patching trials at the edges of the cycle, i.e. instead of making patching trials at cycle edges C1, C2,...,Cl, it only does so at edges C2k+1C2k+2, for integer k. It is further easy to see that the cost of this algorithm is upper bounded by two times a truncated geometric random variable of parameter p2 n. Finally, we bound the mean of the truncated geometric variable by the mean of a complete geometric variable, yielding a final bound of 2/p2 nfor E[TP]. For the proof of the total time complexity of Phase 3, we shall make use of the following probabilistic result: Lemma 4.6. Let Smbe the supremum of mindependent and identically distributed geometric variables having parameter p= 2m−1ln m. We have: E[Sm]∼m 2³1 + γ ln m´, where γis Euler’s constant (0.577...). Sketch of the proof. The full proof is omitted but, in short, we prove the convergence of Smto a Gumbel distribution, we compute the rate of convergence, and we analyze the convergence of moments. 9