IMFM Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA Preprint series Vol. 48 (2010), 1115 issn 2232-2094 EMBEDDING OF COMPLETE AND NEARLY COMPLETE BINARY TREES INTO HYPERCUBES Aleksander Vesel Ljubljana, March 12, 2010 Embedding of complete and nearly complete binary trees into hypercubes Aleksander Vesel Faculty of Natural Sciences and Mathematics, University of Maribor Koroska cesta 160, 2000 Maribor, Slovenia vesel@uni-mb.si ti - Abstract A new simple algorithm for optimal embedding of complete binary trees into hypercubes as well as a node-by-node algorithm for embedding of nearly complete binary trees into hypercubes are presented. Keywords: embedding; complete binary tree; hypercube; algorithm 10 o 1. Introduction and preliminaries Hypercubes and binary trees are omnipresent in computer science. In particular, hypercubes are very popular model for parallel computation, because of their regularity, recursive structure and the ease of routing. On the other hand, the binary tree can represent the basic computational structure of divide-and conquer or branch-and-bound algorithms. In many cases however, it is more suitable that the internal CO structure of an algorithm is modeled by a more general structure - a nearly complete binary tree. CSI In this paper we consider the problem of embedding the (nearly) complete binary tree in the hypercube. This problem develops in the implementation of divide-and conquer algorithms in a hypercube network, CO e.g. see [2, 4]. An embedding is a mapping from the guest graph, representing the communication l-H structure of the processes, into the the host graph, representing the communication network of the processors. Therefore, the problem of allocating processes to processors in a multiprocessor system is fc also known as the mapping problem. A tree is a connected acyclic graph. One vertex is distinguished and called the root. A vertex of degree one is called a leaf of the tree if it is not the root. The level of a vertex v in a tree is the number of vertices on the simple path from the root to v. Note that the level of the root is one. The height of a 5H tree T is the largest level of a vertex in T. A vertex u is called a child of v if u is adjacent to v and the CO level of u is bigger then the level of v. If u is a child of v then v is called the parent of u. A full binary tree is a tree in which every node other than the leaves has two children. A full binary "Jh tree is ordered, i.e. we distinguish between left and right children. A complete binary tree is a full binary tree in which all leaves are at the same level. A nearly complete binary tree of height h is composed of a complete binary tree of height h — 1 and with some nodes at level h. The hypercube of order d and denoted Qd is the graph G = (V, E) where the vertex set V(G) is the Preprint submitted to Elsevier February 25, 2010 o 00 set of all binary strings u(1)u(2) ... u(d), G {0,1}. Two vertices x, y G V(G) are adjacent in Qd if and only if x and y differ in precisely one place. An isomorphic embedding (or just an embedding ) of a graph G(V, E) into a graph H(V', E') is an injection f : V ^ V' such that if (u,v) is an edge in E(G) then (f (u),f (v)) is an edge in E'(H). For binary vectors s,t G {0,1}" let s © t denote the coordinate wise addition modulo two, e.g. 100011 © 000001 = 100010. Let e" be the binary vector (u1, u2,..., un) with x» = 1 and xj =0, j = i. If s is a binary vector of length n, then we will call the operation e" © s a reflection. We will also use the "+" symbol as the concatenation operator, i.e. s +1 joins two binary vectors s and t end to end. If we concatenate a binary vector with a single bit (0 or 1), than we call this operation a projection. For a binary vector s of length n, s + 0 and s + 1 are projections of s into two disjoint hypercubes of order n which compose Qn+1. It is a natural question to ask for an embedding into a hypercube with the least order. The minimum h required for an embedding from a graph G into Qh is called the cubical dimension of G. Deciding whether there exists an embedding of a given tree into a hypercube of a given dimension is known to be NP-complete [3]. Moreover, even in case of trees with bounded degrees, their cubical dimensions are unknown in most cases. I Obviously, if G is a graph such that 2h > |V(G)| > 2h-1, then the cubical dimension of G is at least h. However, it is well known that the complete binary tree on 2h — 1 vertices cannot be embedded into Qh, i.e. into its "optimal" hypercube. Havel in 1984 conjectured that every binary tree T with 2h > |V(T)| > 2h-1 vertices has an embedding CO into Qh+1. The conjecture is still open, but there are many partial results supporting this assertion. It has l-H been showed, for example, that a complete binary tree of height h can be embedded into the hypercube of order h +1, e.g. [2, 4]. This paper present a new simple algorithm which embeds a complete binary tree of height h into the hypercube of order h +1. This algorithm is presented in Section 2. Moreover, the algorithm is the basis for the embedding of nearly complete binary trees of height h into Qh+1, which is presented in Section 3. CD 2. Complete binary tree m Let Ch denote the complete binary tree of height h. Let also rh denote the root of Ch and let Clh and Ch denote the left and the right subtree of Ch, a respectively. Obviously, Clh and Ch are both complete binary trees of height h — 1. Let also define the mapping al : V(Clh) ^ V(Ch-1), where for a vertex v G Clh its image al(v) denote the corresponding vertex of Ch-1 in a natural way, e.g. if v is the root of Clh, then al(v) = rh-1. Analogously we define the mapping 3. Formally, 3h : V(Ch) ^ {0,1}h+1 is the mapping, such that 33 maps the vertices of C3 as depicted in Fig. 1, while for h > 3 the mapping is given by 0 o 1 CO ^ CO CO 3h(v) = 0h+1, 3h — 1 ((v)) + 1, V = Th v e V(Ch) 3h—1(ff;(v)) © 10h—1 +0, V e V(Ch) and h is even 3h—1(o-;(v)) © 0h—3100 + 0, v e V(Ch) and h is odd . For any v of Ch, the string 3h(v) will be also called a codeword defined by 3h in the sequel. Theorem 1. Let h > 3. Then 3h makes an embedding of the complete binary tree of height h in the hypercube of order h +1. 00*00 101 000 10* 1000 10*0001 00* 001 00* 1010 0010011 00* 00010 101 00011 CO CD $H CD CO U a CD U 00* 001100 00* 000101 10* 001110 10*000111 10*00011 10*001110 10*000111 00*00111 00* ( 00110 00*001111 10*0001010 00*0001011 00* 0001110 10* 0001111 00 0001110 10* 0001111 10* 0001100 00 0001101 Figure 2: Codewords derived from 00i0 when i is even The basis of the proof is the following lemma. Lemma 1. Let h > 3. Then 3h(v) = 0h+1 if and only if v is the root of Ch. Proof. If v is the root of Ch, then by the definition 3h(v) = 0h+1. Therefore we only have to show that if v is not the root of Ch, then 3h(v) = 0h+1. Note first, that the recursive definition of 3h implies, that if A o u 10 0 o 1 CO ^ CO CO m CD $H CD m u a CD U v is not the root of Ch, then any 3h(v) is derived as a sequence of projections and reflections either from the root of the Ci+i, i.e. 3i+i(ri+i) = 00*0, h > i > 3, or from a codeword defined by 33. Suppose first that 3h(v) derives from 00*0. Suppose also that i is even. Some of the codewords derived from 00*0 can be seen in the tree depicted in Fig. 2. The root of the tree is 00*0, while the left and the right child of 00*0 is obtained as a codeword derived from it in the left and the right subtree of Ci+2, respectively. Analogously, the left and the right children of 10*000 and 00*001 are codewords in C*+3, etc. Note that the definition of 3j for j > 4 implies that 3j (v) is derived from a codeword s of Cj-1 such that either the first or the (j — 3)-th bit of s is reversed. It follows that from a codeword s of Cj-1 with 1 on at least one of the places: 2, 3,..., j — 4, a codeword of the form 0h+1 cannot be derived. Since every leaf of the tree from Fig. 2 in at least one of those places possesses entry 1, it follows that 0h+1 cannot derive from 00*0 if i is even. It is not difficult to see that a similar tree (having leaves of length j with 1 on at least one of the places 2, 3,..., j — 4) can be derived for 00*0, where i is odd. For 3h (v), which derives from a codeword defined by 33, observe first that all codewords of the left subtree of C3 depicted in Fig. 1 posses 1 at the second place, which implies that 0h+1 cannot be derived from any of them. For 3h(v) derived from a codeword of the left subtree of 33, observe the trees depicted in Fig. 3. From the same arguments as above we now conclude that 0h+1 cannot derive from any codeword defined by 33 and the proof is complete. 0001 1001 0011 10010 00011 00010 10011 101100 100101 001110 000111 001100 000101 101110 100111 100100 101101 000110 001111 0001010 1001011 1001110 0001111 1001010 0001011 0001110 1001111 0001000 1001001 1001100 0001101 Figure 3: Some codewords derived from ,3 Proof (of Theorem 1). The proof is by induction on h. The claim obviously holds for 33. Suppose also that the claim holds for h. Note first that projections maps the vertices of Clh+1 and Ch+1 into two disjoint hypercubes. Moreover, reflections of an embedding in a hypercube preserve Hamming distance. Therefore 3h+1 is an embedding of Clh +1 and C£+1 in the hypercube of order h + 1. Finally, since the root of Ch+1 and the root of Clh+1 (as well as Ch+1) differ in precisely one bit, we conclude that 3h+1 embeds Ch+1 into Qh+1 and the proof is complete. □ Theorem 1 is the basis for the algorithm to compute the optimal embedding of the complete binary tree of height h in Qh+i. We first present the algorithm to calculate the embedding of the complete binary tree of height h from the embedding of the complete binary tree of height h — 1. It is assumed in the algorithm, that if v is an arbitrary node of a complete binary tree T, then b(v) is the codeword of v and p(v) a parent of o v in T. Furthermore, r denote the root of T and T; and Td denote the left and the right subtree of T, J-i O c^ c^ A o u respectively. 10 Procedure NEW TREE input: h, T, b {T is a complete binary tree of height h > 3, b is the embedding of the complete binary tree of height h — 1 } output: b { The embedding of the complete binary tree of height h } o begin traverse Tr from level h to level 2 and for every v G Tr do b(v) := b(p(v))) + 1; o c^ b(v) := b(p(v)) 0 10h-i + 0; CSI CSI m if h mod 2 = 0 then traverse T; from level h to level 2 and for every v G T; do else traverse T; from level h to level 2 and for every v G T; do b(v) := b(p(v))) 0 0h-3100 + 0; r := 0h+1; { The new root of T } end. We next describe the algorithm to compute the optimal embedding of the complete binary tree of height h in a hypercube. Procedure CODES • I input: h {height of a tree, h > 3} output: T, b { T is a complete binary tree of height h with the embedding b } begin 1. T := complete binary tree of height 3. 2. Determine b(v) for every node of v G T as in Fig. 1; Jh 3. for i := 4 to h do begin Augment T with new level of nodes to obtain the complete binary tree of height i; 10 o NEW TREE(i, T, b); end. Theorem 2. Let h > 3. Then CODES embeds a complete binary tree of height h into Qh+1 in linear-time and space. o Proof. The correctness of the algorithm is by induction on h. If h = 3, then the embedding is given in Step 2, the correctness of which can be verified by Fig. 1. Assume now that for i = h — 1 the algorithm correctly compute the embedding of T. In other words, when NEW TREE is called in Step 3 for i = h, the vector b corresponds to the embedding fih-1. Moreover, for a node v G T; (v G Tr), the old value of b(p(v))) corresponds to ph-1((Jr(v)) (fth-1(ai(v))). Therefore, since the nodes of T are traversed from the last level to the roots of the subtrees and since NEW TREE accurately follows the definition of we can conclude that the embedding is correct. T, p, and b can be obviously represented in linear space, therefore we only consider the time complexity. Let then n = 2h — 1 denote the number of nodes of a complete binary tree of height h. Note first that NEW TREE computes the embedding b in time which is linear in the size of T. Since the number of vertices of T in i-th iteration of the for loop equals 2® — 1, the total number of steps of the algorithm is given by □ ^ 2® — 1 = 2h+1 — 12 = O(n) . i=4 This argument completes the proof. 3. Near complete binary tree In this section we present a simple node-by-node algorithm for constructing an embedding of a nearly complete binary tree into a hypercube. We assume that in each time step a nearly complete binary tree CD can grow for one node, which is inserted at the last level of a tree. Note, that in [1] a somewhat similar approach has been studied, where the complete binary tree grows by a complete level of its leaves. The algorithm presented herein compute the map of the nodes of a new tree using the map of their £ parent node. Moreover, if a new node does not change the height of a tree, the old nodes need not to be Jh remapped. CD The algorithm of the previous section implies, that the embedding of a complete complete binary tree of height h can be performed by using the embedding of the complete complete binary tree of height h — 1, such that the embedding of a node v is computed from the "old" embedding of its parent node. o c^ £ CO CO This observation leads to a node-by-node algorithm for embedding of nearly complete binary trees into hypercubes. The algorithm augments a given nearly complete binary tree with one node, which is inserted at the level h and computes the mapping of the augmented tree. We will show that in the majority of cases the algorithm is able to determine the embedding of the augmented tree by simply expanding the embedding with the map of the new node. Moreover, the map of the new node can be o computed with ease from the map of its parent node. J-i If a nearly complete binary tree T of height h with embedding into Qh+1 is augmented with one new node, then for the resulting nearly complete binary tree T' the embedding into Qh+1 (or Qh+2, if the height of T' is h + 1) is computed. The new node can be (i) a leaf at level h, if T is not complete or (ii) a leaf at level h + 1, if T is complete. Let 3h be a mapping that determines a binary string of length h + 1 to every vertex of the complete ary tree of height the following lemma. binary tree of height h > 3 as defined in Section 2. In order to obtain the embedding for T' we first show C^ Lemma 2. Let for h > 3, v be a leaf of Ch and u the parent of v in Ch. Then CSI CO , I 3h(u) e 10h, v is the left child of u 3h(v) = { 3h(u) e 001h-30, v is the right child of u. Proof. The proof is by induction with respect to h. The claim obviously holds if h = 3 as can be seen in Fig 1. Let us denote v a leaf of Ch+1 and u the parent of v. If v (and u) is in the right subtree of Ch+1, then by inductive hypothesis 3h(°V (v)) and 3h(ar (u)) differ either in the first bit, if v is the left child of u, or in the third bit, if v is the right child of u. It is straightforward to see now that 3h+1(v) = 3h(°V(v)) + 1 and 3h+1(u) = 3h(o>(u)) + 1 differ either in the first or in the third bit. If v is in the left subtree of Ch+1, the proof is analogous. □ Jh p(u) denote the codeword of u and the parent of u in T, respectively. In the following algorithm, let for an arbitrary vertex u of a nearly complete binary tree T, b(u) and Procedure NEW NODE • I input: h, T, b, v { b is the embedding of T, h > 3, v is a new node } & output: T, h, b { An augmented tree of height h with the embedding b } u begin 1. if T is complete then begin NEW TREE (h, T, b); lO u CD CO h := h +1; end; 2. Insert v at the level h in T; 3. if v is the left child of p(v) then b(v) := b(p(v))) © 10h; o 1—1 else b(v) := b(p(v))) © 0010h-2; J-i end. In order to obtain the embedding of a nearly complete binary tree with NEW NODE, before the algorithms is first called, Step 1 and Step 2 of CODES have to be executed. T is then the complete binary tree of height 3 with the embedding b. Theorem 3. If T is C3 or a nearly complete binary tree of height h > 3 and b the embedding of T into Qh+1, then NEW NODE correctly embeds T' either (i) into Qh+2, if T is complete or (ii) into Qh+1, if T is not complete. (i) into Qh+2, if T is complete or Proof. Assume that T is either C3 or an arbitrary near complete binary tree of height h > 3 and b its embedding into Qh+1. If T is not complete, then the correctness of the algorithm follows from Lemma 2. Let then T be a complete binary tree. When NEW TREE is called in Step 1, the value of h is not yet incremented, i.e. the output of the procedure is the complete tree of height h with the embedding £ into Qh+2. However, in Steps 2 and 3, T is first augmented with a new node at level h +1 and then the embedding into Qh+2 of the resulting nearly complete tree of height h + 1 is computed. The following concluding comment concerning the time complexity of the algorithm is on order. The algorithm remaps the nodes of T only if T is a complete binary tree. In other cases a remapping is not ^ performed. a^y the embedding of a new node depends only on the map of its parent node and can CD be performed in constant time. However, even in the case when remapping is needed, the computation of the new embedding can be done independently in each node v such that only the codeword of a parent node of v is used. It follows that the remapping can be computed on the hypercube in parallel in constant time. u a References U cu [1] V. Heun and E.W. Mayr, Optimal dynamic embeddings of complete binary trees into hypercubes, J. Parallel Distrib. Comput. 6 (2001) 11110-1125. A o u [2] A.S. Wagner, Embedding the complete tree in the hypercube, J. Parallel Distrib. Comput. 20 (1994) 241247. [3] A.S. Wagner, D.G. Corneil, Embedding trees in a hypercube is NP-complete, SIAM J. Comput. 7 (1990) 570-590. [4] A. Y. Wu, Embedding of Tree Networks into Hypercubes, J. Parallel Distrib. Comput. 2 (1985) 238-249. lO 0 o 1 CO £ CO CO m CD $H CD m u a CD U fc