Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes
Fabian Kuhn Konstantinos Panagiotou Pascal Su
cs.DS

Serious Games Application for Memory Training Using Egocentric Images
    Gabriel Oliveira-Barra1 Marc Bolaños1 Estefania Talavera1,2 Adrián Dueñas1 	Olga Gelonch3 Maite Garolera3
    December 30, 2023
=============================================================================================================




  We investigate the nearest common ancestor (NCA) function in rooted trees. As the main conceptual contribution, the paper introduces universal trees for the NCA function: For a given family of rooted trees, an NCA-universal tree S is a rooted tree such that any tree T of the family can be embedded into S such that the embedding of the NCA in T of two nodes of T is equal to the NCA in S of the embeddings of the two nodes.

  As the main technical result we give explicit constructions of NCA-universal trees of size n^2.318 for the family of rooted n-vertex trees and of size n^1.894 for the family of rooted binary n-vertex trees. A direct consequence is the explicit construction of NCA-labeling schemes with labels of size 2.318log_2 n and 1.894log_2 n for the two families of rooted trees. This improves on the best known such labeling schemes established by Alstrup, Halvorsen and Larsen [SODA 2014].
  
  


Keywords: Rooted Trees, NCA, Nearest Common Ancestor, Lowest Common Ancestor, Universal Trees, Labeling Schemes, Embedding Schemes





§ INTRODUCTION



The nearest common ancestor[In the literature, the nearest common ancestor of two vertices in a rooted tree is sometimes also referred to as the lowest or least common ancestor (LCA).] (NCA) of two vertices u and v of a rooted tree T is the first common vertex of the paths connecting u and v to the root of T. Finding the nearest common ancestor appears as an essential operation in many algorithms and applications (see for example the survey by Alstrup, Gavoille, Kaplan, and Rauhe <cit.>).



  
NCA-Universal Trees. The present paper introduces the notion of NCA-universal trees as a novel tool to study and algorithmically deal with the NCA function in rooted trees. We define an NCA-universal tree S for a family of rooted trees 𝒯 as such that every tree T∈𝒯 can be embedded into S such that the NCA function is preserved by the embedding. More formally, an embedding of T into S is an injective mapping φ_T of V(T) into V(S) such that the embedding function φ_T and the NCA function commute.



  
NCA-Labeling Schemes. As an immediate application of an NCA-universal tree S for a family 𝒯 of rooted trees, S directly implies an NCA-labeling scheme <cit.> for the family 𝒯. Generally, a labeling scheme is a way to preprocess the structure of a graph to later allow simple and fast queries. A labeling scheme consists of an encoder and a decoder, where the encoder must be able to label a family of graphs such that the decoder can answer queries, given just the labels and no additional information about the underlying graph. More specifically, an NCA-labeling scheme assigns a unique label to each node of a rooted tree T such that given the labels of two vertices u and v of T, it is possible to compute the label of the NCA of u and v in T. If an NCA-univeral tree S for a family 𝒯 of rooted trees is given, we can get an NCA-labeling scheme for 𝒯 as follows. Let |S| be the number of vertices of S and assume that the vertices of S are labeled from 0 to |S|-1 in a arbitrary fixed way. Given an embedding of a tree T∈𝒯 into S, we then get the labeling of a vertex v of T by using the label of the vertex x of S to which v is embedded. The size of the labels (in bits) of the labeling scheme is therefore exactly ⌈log|S|⌉. We remark that throughout the paper, all logarithms are to base 2.



  
Contribution. We show that the family of all rooted trees with at most n vertices has an NCA-universal tree of size O(n^2.318) and that the family of all binary rooted trees with at most n vertices has an NCA-univeral tree of size O(n^1.894). This implies that the families of rooted n-vertex trees and of rooted n-vertex binary trees have labeling schemes with labels of size 2.318log n and 1.894log n, respectively. This improves on the best previous NCA-labeling schemes that were developed by Alstrup, Halvorsen and Larsen <cit.> and which require labels of size 2.772log n for general rooted trees and of size 2.585log n for binary rooted trees. In <cit.>, it is also shown that any NCA-labeling scheme for general n-vertex rooted trees requires labels of size at least 1.008log n.

As we show how to explicitly construct the NCA-universal trees, our labeling schemes are constructive. Note that the best NCA-labeling schemes of <cit.> are not constructive and that the best previous constructive NCA-labeling scheme for n-vertex rooted trees requires labels of size 3log n. Further, our NCA-labeling schemes are efficient, the embedding of a rooted tree into the constructed NCA-universal tree can be computed efficiently and a single query can be answered in time O(log^2n) (O(log n) for binary trees). We believe that our new NCA-labeling schemes are not only interesting because they improve upon the best existing schemes, but also because our approach leads to more intuitive and significantly simpler constructions.



  
Related Work. Graph labeling schemes are an elegant way
to store structural information about a graph. As every vertex is only
assigned a small label, the information is stored in a completely
distributed way and graph labelings therefore are particularly
interesting in a distributed context, where labeling schemes are used for various kinds of graph queries <cit.>. In addition, labeling schemes can be used in a context where extremely large graphs are processed and where accessing the data is expensive. To answer a pair-wise query, only the two labels of the corresponding vertices need to be accessed.


The first labeling schemes that appear in the literature are adjacency labeling schemes (given the labels of two vertices, determine whether the vertices are adjacent). They were introduced among others by Breuer <cit.> and Folkman <cit.>. In the context of adjacency labeling schemes, it is well known that they are tightly connected to induced universal graphs. A graph G is an induced universal graph for a graph family ℋ if G contains every graph H∈ℋ as an induced subgraph. Induced universal graphs were first described by Rado <cit.> and Kannan et al.<cit.> noted the equivalence between adjacency labeling schemes and induced universal graphs.

When considering the family of rooted trees we are interested in  different queries such as whether a vertex is an ancestor of the other. Ancestry labeling has been studied and labeling schemes of size log(n) + Θ(log(log(n))) are known to be tight <cit.>. If the tree has low depth, then a scheme of size log(n) +2log(d) +O(1) is known, where d is the depth of the tree <cit.>.

For NCA-labeling schemes, a linear-size labeling scheme that answers queries in constant time was introduced by Harel and Tarjan in <cit.>. In the following, there was a series of significant improvements in <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.> and most recently in <cit.>. In particular in <cit.>, a lower bound for NCA labeling schemes of 1.008 log n is shown, which separates NCA-labelings, that need labels of size log n + Ω(log n), from ancestry labeling schemes, where labels of size log n + O(loglog n) are sufficient. 

There is concurrent work by Gawrychowski and Łopuszański <cit.> who reach the exact same bounds for labeling schemes and construct almost identical universal trees as we do. The proof method is a bit different and in their paper they also have lowerbounds for the size of a universal tree for the NCA function.

  



  
Outline.
The rest of the paper is organized as follows. In the remainder of this section, we first formally define the problems and state our results in <Ref>. In <Ref>, we first prove a simpler upper bound of O(n^2) on the size of NCA-universal trees for the family of binary rooted trees. We extend the construction of <Ref> to obtain the stronger and more general results stated above in <Ref>. Finally, in <Ref>, we sketch how to efficiently implement our labeling scheme and in <Ref>, we conclude the paper and discuss some open issues.




 §.§ Definitions



We next define the necessary graph-theoretic concepts and notation and we in particular formally introduce the notion of universal trees for the NCA function. In the following let 𝒯_n be the family of unlabeled rooted trees with at n vertices and ℬ_n the family of unlabeled rooted binary trees with n vertices. 


 In a rooted tree T=(V,E) a vertex u is an ancestor of a vertex v if u is contained in the (unique) path from v to the root of T.  


Note that according to the above definition, a node u is an ancestor of itself.


Let T=(V,E) be a rooted tree. For a pair of vertices u and v their nearest common ancestor (NCA) _T(u,v) is the unique common ancestor that is furthest from the root of T. 

With this notation at hand we can define the notion of a universal tree for NCA.

A rooted tree S is called an NCA-universal tree for a family of rooted trees 𝒯, if for every tree T∈𝒯 there is an embedding function φ_T:V(T)↦ V(S) such that φ_T commutes with the NCA function, i.e., for all u,v∈ V(T), φ_T(_T(u,v)) =_S(φ_T(u),φ_T(v)).


Hence, the embedding has the property that the NCA of two nodes u and v of T is mapped to the NCA of φ_T(u) and φ_T(v) in S. Note that we do not require the root of T to be embedded to the root of S. In the following, a rooted tree that is universal for the NCA function is also called an NCA-universal tree. 


An NCA-labeling scheme for a family of rooted trees 𝒯 is a pair of functions called the encoder (f) and decoder (g) with f : { v|v∈ T ∈𝒯}↦ [m] and g:[m]× [m] ↦ [m] satisfying the following properties.

  
  * for every T∈𝒯 and every u,v∈ V(T), f(u)≠ f(v) and
  
  * for every T∈𝒯 and every u,v∈ V(T), g(f(u),f(v))=f(_T(u,v)).

For a node v∈ T∈𝒯, f(v) is called the label of v. The size of the labeling scheme defined by f and g is ⌈log m⌉, i.e., the number of bits required to store the largest label.


Given an NCA-universal tree S for a family of rooted trees 𝒯, we directly obtain an NCA-labeling scheme for 𝒯.



  Let S be an N-vertex rooted tree that is universal for the NCA function and the family 𝒯 of rooted trees. Then, there exists an NCA-labeling scheme of size ⌈log N⌉ for 𝒯.


  We assign unique names from 0 to N-1 to the N vertices of S. Consider a tree T∈𝒯 and let f be an embedding of T into S. The label of a vertex v of T is the name assigned to vertex f(v) of S. Given the labels x_u∈0,…,N-1 and x_v∈0,…,N-1 of two nodes u and v of T, the decoder outputs the name x_w∈0,…,N-1 of the NCA of the vertices u' and v' with names x_u and x_v in S.




 §.§ Main Results


Our main result is an explicit construction of universal trees for the families of all trees and binary trees with n vertices. The same bounds can be found in the concurrent work of Gawrychowski and Łopuszański <cit.>.


Let n∈ℕ. Then:

	
  * There is a rooted tree S_n of size less than n^ 2.318 that is universal for the NCA function and the set 𝒯_n of rooted trees of size n.
	
  * There is a rooted tree S_n^bin of size less than n^1.894 which is universal for the NCA function and the set ℬ_n of rooted binary trees of size n.


The proof can be found in Section 3. The direct implication of this for labeling schemes is summarized in the following statement.


For any n∈ℕ there exists an NCA-labeling of size less than 2.318  log n and an NCA-labeling for binary trees of size less than 1.894  log n.

This is an improvement of the current best known bound of 2.772  log n from <cit.>. Further for the specific case of binary trees of particular interest is that the constant is now below 2 and therefore will likely not be an integer. 
 This is exactly what we have shown in <Ref> and therefore follows from <Ref>.
Although this is just an existential proof, from the construction we will see later, it is clear that a reasonably fast algorithmic implementation is possible and we will give a sketch in <Ref>.





§ BASIC UNIVERSAL TREE CONSTRUCTION



The NCA-universal trees of <Ref> are constructed recursively. 
Before proving the general statements of <Ref>, we describe a simpler, slightly weaker construction that provides an NCA-universal tree of size O(n^2) for n-vertex binary trees. The full constructions required to prove <Ref> appears in <Ref>.


  For any n∈ℕ there exists a rooted tree S_n of size
  less than n^2 which is universal for the NCA function and the
  rooted binary trees of size at most n.


Our recursive universal tree construction requires two kinds of NCA-universal trees. In addition to ordinary unlabeled rooted trees, we also need to define NCA-universal trees for the family of rooted binary trees where one leaf node is distinct (marked). Recall that ℬ_n denotes the set of all n-vertex unlabeled rooted binary trees, so let ℬ_n' denote the family of unlabeled rooted binary trees on at most n vertices and with one marked leaf. 



A rooted tree S' with one marked leaf vertex w is called a NCA-universal tree for a family of rooted trees 𝒯' with one marked leaf if for every tree T∈𝒯', there exists an embedding function φ_T : V(T) ↦ V(S') that maps the marked leaf of T to the marked leaf w of S' and where φ_T commutes with the NCA function, i.e.,  φ_T(_T(u,v)) =_S(φ_T(v),φ_T(u)) for all u,v∈ T.

As in <Ref>, we do not require that the root of T is mapped to the root of S'.







  
Overview of the Construction. The construction of the NCA-universal tree for binary rooted trees is done recursively as illustrated in <Ref>. The universal tree S_n for binary trees of size at most n consists of three NCA-universal trees for binary trees of size at most n/2, where one of these three universal trees needs to work for the more general family trees with one marked leaf vertex. Universal trees for the family of n-vertex trees with a marked leaf are constructed recursively in a similar way. They consist of two NCA-universal trees for n/2-vertex binary trees with a marked leaf and of a single NCA-univeral tree for ordinary n-1-vertex binary trees (see <Ref>).

In order to show that the recursive construction of <Ref> results in an NCA-universal tree we need to argue that any n-vertex binary tree T can be embedded. To achieve this, we show that any rooted tree T has a vertex v such that v splits T into three subtrees of size at most n/2. Vertex v is then embedded to the vertex marked in red in the left part of <Ref>. The three subtrees of T induced by v are then embedded recursively into the three parts of the universal tree construction. Further, we need to show that any rooted tree T with a marked leaf can be partitioned in a similar way to be consistent with the recursive structure in the right part of <Ref>. In the following, we first give the basic technical lemmas required to partition n-vertex trees T into the required smaller subtrees. Based on these partitioning results, we the analyze the recursive NCA-universal tree construction in more detail and prove <Ref>. As the same partitioning lemmas will also be needed in the general NCA-universal tree constructions in <Ref>, they are stated more generally than what we require for the simple construction of the present section.



  
  For every rooted n-vertex tree T and for every
  parameter λ∈ (0,1], there exists a vertex v∈ V(T)
  such that removing the edges from v to its children splits the
  tree into components such that each component rooted at a child of
  v has size at most ⌊ (1 - λ) · n ⌋ and
  such the remaining component containing v and the root of T has
  size at most ⌈λ· n ⌉.


  We determine v using the following simple iterative
  procedure. We initialize v to be the root of T. We stop the
  procedure as soon as v satisfies the conditions of the lemma. For
  some vertex u of T, let 𝑠𝑖𝑧𝑒(u) be the number of
  vertices in the subtree rooted at u. If v does not split the
  tree as required, we let w be the child vertex of v that
  maximizes 𝑠𝑖𝑧𝑒(w) and we set v:=w. Since v goes from
  being the root of T to being a leaf of T during this process,
  the component containing the root goes from being of size 1 to a
  set of size n. We claim that for the last vertex v where the
  connected component of the root is still of size at most
  ⌈λ· n ⌉, the lemma holds.
  
  Clearly, the component with the root is of size at most
  ⌈λ· n ⌉ and it thus suffices to show that
  all the subtrees of v are of size at most
  ⌊ (1-λ)n⌋. Assume for contradiction that v has a
  child w such that
  𝑠𝑖𝑧𝑒(w)≥ 1+ ⌊ (1-λ)n⌋. Then,
  removing all subtrees of w from T would result in a component of
  size at most n-⌊ (1-λ)n⌋=⌈λ n⌉
  and thus v would not be the last vertex for which the connected
  component of the root is of size at most ⌈λ n⌉.



For trees with a marked leaf we can get a similar tree splitting lemma.


  
  Given a rooted n-vertex tree T with one marked leaf vertex w
  and a parameter λ∈(0,1]. If n≥1/1-λ, there exists a vertex
  v∈ V(T) such that when removing the edges connecting v to its
  children, T is split into components satisfying the following
  properties. The component containing the root of T and vertex v
  has size at most ⌈λ n⌉, the component containing
  the marked leaf w has size at most ⌊ (1-λ)n⌋,
  and all other components have size at most n-1.



  Let r bet the root vertex of T. We choose v to be last vertex
  on the path from r to w such that when removing the subtrees of
  v, the remaining component has size at most
  ⌈λ n ⌉. ⌈λ n ⌉<n, so v
  cannot be a leaf and thus v≠ w. Let v' be the root of the
  subtree of v containing w. To prove the lemma, it suffices to
  show that the subtree rooted at v' has size
  𝑠𝑖𝑧𝑒(v')≤⌊(1-λ)n⌋. For the sake of
  contradiction, assume that
  𝑠𝑖𝑧𝑒(v')≥⌊(1-λ)n⌋+1. In this case,
  the total size of all subtrees of v' is at least
  ⌊(1-λ)n⌋ and thus removing all subtrees of v'
  would leave a component of size at most ⌈λ
  n⌉. This contradicts the assumption that v is the last
  vertex on the path from r to w for which this is true.





  For every integer n≥ 1, we show how to construct an
  NCA-universal tree S_n for the family ℬ_n of
  n-vertex rooted binary trees and an NCA-universal tree S_n' for
  the family ℬ'_n of n-vertex binary rooted trees with
  one marked leaf. We will prove by induction on n that
  |S_n|≤ n^2 and that |S_n'|≤ 2n^2-1 for all n≥ 1.

  For the induction base, note that S_1 and S_1' clearly need to
  only consist of a single vertex and we thus have
  |S_1|=|S_1'|=1. Thus, the bounds on |S_n| and |S_n'| hold for
  n=1.
  For the induction step, assume that n≥ 2 and that
  |S_k|≤ k^2 and |S_k'|≤ 2k^2-1 for all
  1≤ k<n. We build the two NCA-universal trees S_n and S_n' by using smaller NCA-universal trees as given in
  <Ref>. That is, S_n is composed of one copy of S_⌈ n/2⌉' 
  and two copies of S_⌊ n/2⌋  and S_n' is composed of one copy of
  S_⌈ n/2⌉', S_⌊ n/2⌋', and S_n-1. We need to show
  that the constructed trees S_n and S_n' are in fact
  NCA-universal trees and that they satisfy the required size
  bounds. We first show that the trees are or the right size. Using
  the induction hypothesis, we have
  
    |S_n|
            =    |S_⌈n/2⌉'| +
              2·|S_⌊n/2⌋|
         ≤ 2 ·⌈n/2⌉^2-1 + 2·⌊n/2⌋^2
         ≤ n^2,  and
    
        |S_n'|
            =     |S_⌈n/2⌉'| +
               |S_⌊n/2⌋'| +
               |S_n-1|
                ≤           2·⌈n/2⌉^2 - 1+
               2·⌊n/2⌋^2 -1 +
               (n-1)^2
                ≤ 2 n^2-1.

  It thus remains to prove that the recursive construction of S_n
  and S_n' allows to find a proper embedding for every
  T ∈ℬ_n into S_n and every T' ∈ℬ_n
  into S_n', respectively.

  To show this, we use <Ref> and <Ref>. We
  first show how to construct an embedding φ_T of a binary
  n-vertex tree T∈ℬ_n into S_n. For this purpose,
  we apply <Ref> with parameter λ=1/2 to tree
  T. Let v∈ V(T) be the vertex of T that splits the tree such
  that the part containing the root of T and v has size at most
  ⌈ n/2⌉ and such that all other components have size at
  most ⌊ n/2⌋. For the embedding take the splitting
  vertex v∈ T given by <Ref> which will be
  embedded to the marked vertex of the copy of
  S_⌈n/2⌉ ' (cf.  <Ref>). Consider the three components of T
  after splitting. By the induction hypothesis there is an embedding
  function to embed the child components (components below the
  splitting vertex v) into the two copies of
  S_⌊n/2⌋. Then we take the component with
  the root and the marked vertex to get a tree with a single marked
  leaf of size at most ⌈n/2⌉ and the induction
  hypothesis again provides with an embedding function of this
  component into S_⌈n/2⌉ '. The embedding is
  depicted in <Ref>.

  

  To see that the NCA-function for any two vetices u_1 and u_2 and
  the described embedding function φ_T commute, we need that
  _S_n(φ_T(u_1), φ_T(u_2)) =
  φ_T(_T(u_1,u_2)). This can be verified through the
  following case analysis considering the three components after the
  splitting process.  If
  u_1 and u_2 are in the same component, then we have embedded them
  into the same subtree and by the induction hypothesis, we have
  φ_T(_T(u_1,u_2))=_S_n(φ_T(u_1),φ_T(u_2)).
  If u_1 and u_2 are in different child components, we have
  _T(u_1,u_2)=v and the embedding is therefore also correct
  because is embedded to the vertex marked in red in
  <Ref>. Finally, if u_1 is from the component
  containing the root and vertex v and u_2 is a vertex from
  a child component, we have _T(u_1,u_2)=_T(u_1,v) and
  similarly  _S_n(φ_T(u_1),φ_T(u_2))=_S_n(φ_T(u_1),φ_T(v))
  and the embedding is therefore again correct by the induction
  hypothesis (applied to the partial embedding into the subtree
  S_⌈ n/2⌉').

  For the family of n-vertex binary trees with a marked leaf, the
  embedding into the recursively constructed tree S_n' (cf.  <Ref>) works in similar way. Let T' be a
  binary tree of size at most n and with a marked leaf. We apply
  <Ref> with parameter λ=1/2 to T' to obtain a
  vertex v∈ V(T') that splits T' into a) a subtree of size at
  most ⌈ n/2⌉ that contains the root of T' and that
  contains v as a leaf vertex, b) a subtree size at most
  ⌊ n/2⌋ that is rooted at a child of v and contains
  the marked leaf of T', and c) a (possibly empty) subtree of size
  at most n-1 rooted at a child of v. The tree T' is embedded
  into S_n' by embedding vertex v to the center red node
  separating the three recursive subtrees in
  <Ref>. The three subtrees resulting after
  splitting T' are embedded into the three recursively constructed
  subtrees S_⌈ n/2⌉', S_⌊ n/2⌋', and
  S_n-1 in the natural way. The proof that the embedding is
  correct is done in the same way as for the embedding of T into
  S_n. The details of the embedding are illustrated in
  <Ref>.

  






§ GENERAL UNIVERSAL TREE CONSTRUCTION



The proof of the basic construction was handled in detail. We now adjust the construction to improve on the exponent in the size of S_n and to deal with general rooted trees. Throughout the section, we omit floor and ceiling functions. They do not change the calculations significantly, but hinder the readability of the proof.


  As suggested in <Ref> and <Ref>, the
  adjustment of the basic construction can be made by choosing λ≠ 1/2 for the
  size of the splitted components.

  We start with the binary tree case. We apply the same induction as
  in the proof of <Ref>. In the general case, we prove that
  |S_k| ≤ k^β and |S_k'| ≤ c · k^β
  ∀ 1≤ k < n and some constants c and β that will
  be determined later.

    
  

  For the construction of S_n we take S_λ n ' and attach
  copies of S_ (1-λ )n and S_n/2 to the marked
  vertex for some λ∈ (0,1/2]. The construction of
  S_n' remains the same as in <Ref>. For an
  illustration, see <Ref>. Note that although
  in <Ref> the child components can be of size
  (1- λ) · n, the two components together can have size at
  most n, so the smaller of the components is always of size at most
  n/2. We obtain
  
    [                                       |S_n|    ≤ |S_λ n '| + |S_ (1-λ )n| +   |S_n/2  | ≤ c    (λ n)^β + (  (1-λ ) n)^β + ( n/2) ^β                                    !≤   n^β;                                      |S_n'|             ≤ |S_n/2'| + |S_n/2'| +  |S_n |            ≤ c( n/2) ^β + c ( n/2) ^β + n^β                                   !≤ c n^β. ]
 
     We would like to choose β as small as possible. Note that with the second inequality, we obtain

    c( n/2) ^β + c ( n/2) ^β + n^β≤ c n^β

and we thus get that c ≥1/1-2^β-1.

In our construction we are allowed to freely choose λ∈ (0,1/2]. We can thus choose β and λ such that β is minimized and following inequality is still satisfied:

    (1-λ )n^β + c    λ n  ^β +·n/2^β≤  n^β.

To achieve this, we choose λ = 0.296149... and the corresponding β≤ 1.89311.... This proves the claim of <Ref> about binary rooted trees.




In a general tree, a vertex can have many children. Therefore we adjust the construction to deal with this fact as shown in <Ref>. Take any λ∈ (0,1/2]. Let S_n be composed of a copy of S_λ n' and attached to the marked vertex of that tree copies of S_(1-λ)n, S_n/2, S_n/3, S_n/4, etc., up to S_1. Similarly, let S_n' be composed of a copy of S_n/2' and attached to the marked vertex of that tree copies of S_n/2', S_n, S_n/2, S_n/3, S_n/4, etc., up to S_1. 
 
For the embedding, note that we can sort the child components by size.  <Ref> states that any child component is of size at most (1-λ) · n. In addition, the total size of all components cannot add up to more than the entire tree of size n. This implies that after ordering the components by size, the i^𝑡ℎ child component without a marked vertex is of size at most n/i.

With the induction hypothesis that |S_k| ≤ k^β and |S_k| ≤ c · k^β, the recursion gives

    [                                           |S_n| ≤ |S_ (1-λ )n| + |S_λ n '| +  ∑_i=2^n |S_n/i  |   ≤( (1-λ )n)^β + c   (λ n) ^β +( ζ(β) -1)  n^β                                         !≤  n^β;                                          |S_n'|       ≤ |S_n/2'| + |S_n/2'| + ∑_i=1^n |S_n/i  |           ≤ c( n/2) ^β + c ( n/2) ^β + ζ(β) n^β                                       !≤ c n^β, ],
 
where ζ(β) is the Riemann zeta function (ζ(β) =  ∑_i≥1i^-β ). Again we can deduce from the second inequality that c ≥ζ(β) /1-2^β-1. By using λ = 0.341395..., we get that β≤ 2.31757... .

In both constructions, the fact that the NCA function and
the embedding function commute follows in the same way as in the proof
of <Ref>.  This concludes the proof of
<Ref>.




§ IMPLEMENTATION OF THE NCA-LABELING SCHEME




The labeling schemes described in <Ref> can be constructed efficiently. Further, given two labels, the label of the nearest common ancestor can be determined in O(log^2n) time  (in O(log n) time in the binary tree case).

 For R ∈ℝ we write [R] := {x: 1 ≤ x ≤ R}.
In order to assign labels to the vertices of S_n we proceed as
follows. Set s(n) =  n^β, and  recall that |S_n| ≤ s(n) and
|S'_n| ≤ c s(n). Moreover, as depicted in <Ref> the tree
S_n is composed out of the n+1 trees

    T_0     = S'_λ n
    
    T_1     = S_(1-λ)n
    
    T_ℓ    = S_n/ℓ,  where  2 ≤ℓ≤ n.

Define the corresponding counting sequence

    t_-1    = 0 
    
    t_0     = c  s(λ n) 
    
    t_1     = t_0 + s((1-λ)n) 
    
    t_ℓ    = t_ℓ-1 + s(n/ℓ),  where  2 ≤ℓ≤ n.

For S'_n we proceed similarly. As depicted in <Ref> S'_n
is composed out of the n+2 trees

    T'_-1    = S'_n/2
    
    T'_0     = S'_n/2
    
    T'_ℓ    = S_n/ℓ,  where  1 ≤ℓ≤ n.

and the corresponding counting sequence is given by

    t'_-2    = 0 
    
    t'_-1    = cs(n/2) 
    
    t'_0     = t_-1 + cs(n/2) 
    
    t'_ℓ    = t_ℓ-1 + s(n/ℓ),  where  1 ≤ℓ≤ n.

Given these sequences, in order to assign labels to the vertices in
S_n we assign to the vertices of T_i, 0 ≤ i ≤ n the labels in
[t_i] ∖ [t_i-1]. The assignment is performed recursively, in
the sense that as soon the labels in T_i, 0 ≤ i ≤ n  are assigned,
they are translated by an additive ⌈ t_i-1⌉, so that they
all lie (with room to spare) in the required set [t_i] ∖
[t_i-1]. The assignment is performed analogously for S'_n, where
we use the corresponding counting sequence instead.

Given the label of a vertex in S_n, its location in the tree can be
found with this preprocessing in O(log^2 n) time. Indeed, in every step
we have to decide in which of the at most n+2 subtrees we have to branch
to; however, this can be decided with binary search on the sequences
(t_i)_0 ≤ i ≤ n or (t'_i)_-1 ≤ i ≤ n. As the depth of the recursive construction of S_n is
O(log n), the claim follows. 




§ CONCLUSION



We introduced NCA-universal trees and gave simple recursive
constructions of such trees that in particular lead to improved
NCA-labeling schemes for rooted trees. The paper leaves several
interesting open questions. The current upper bound of 2.318log n
bits per label is still quite far from the 1.008log n-bit lower
bound proven in <cit.> and it remains
an intriguing open problem to close this gap. In addition, given that
NCA-universal trees provide an intuitive way to argue about
NCA-labeling schemes, it is natural to ask whether the approach can
lead to optimal NCA-labeling schemes or whether every NCA-labeling
scheme for a given tree family can be turned into an equivalent one
that can be characterized by an NCA-universal tree for the tree
family. The following observation shows that NCA-universal trees are
equivalent to a certain well-structured class of NCA-labeling schemes.

We call an NCA-labeling scheme consistent if any three labels can occur together in some tree. More formally, an NCA-labeling scheme is called consistent if it satisfies the following three properties for any 3 possible labels x, y, and z. In the following, g is the decoder function.


  * If g(x,y)=z, then g(x,z)=z and g(y,z)=z
 (i.e., 
  if z is the NCA of x and y, then z is an ancestor of x and y)

  * If g(x,y)=y and g(y,z)=z, then g(x,z)=z
 (i.e., 
  if y is an ancestor of x and z  an ancestor of y, then also z is an ancestor of x)

  * If g(x,y)=y and g(x,z)=z, then g(y,z)∈y,z

  (i.e., if y and z are ancestors of x, then z is an ancestor
  of y or y is an ancestor of z)



  Every NCA-universal tree S for a given family 𝒯 of trees leads to a consistent NCA-labeling scheme for 𝒯 with labels of size ⌈log|S|⌉. Conversely, every consistent NCA-labeling scheme for 𝒯 and with ℓ-bit labels induces an NCA-universal tree of size 2^ℓ for 𝒯.


  The first claim of the lemma is immediate because S is a tree and therefore any three vertices of S (i.e., any three labels) are consistent.

  For the second claim, define a directed graph G=(V,E) as follows. The vertex set V of G is the set of labels of the given NCA-labeling scheme. Assume that g is the decoder function of the labeling scheme.  We add a directed edge from u∈ V to v∈ V if g(u,v)=v and there is no vertex w such that g(u,w)=w and g(w,v)=v (i.e., if v is the parent of u). We claim that G is a rooted tree.

  First observe that G is acyclic. Otherwise, by using Property (II) several times, we can find three vertices u, v, and w such that g(u,v)=v, g(v,w)=w, and g(w,u)=u. However from Property (II) we then also have g(u,w)=w, a contradiction.

  Second, we show that the out-degree of each vertex of G is at most 1. For contradiction, assume that there exists a vertex u that has out-going edges to v and w. We then have g(u,v)=v and g(u,w)=w and by Property (III) of consistent labeling schemes, we thus also have g(v,w)=w or g(w,v)=v. Thus, one of the two edges (u,v) and (u,w) cannot be in G.

  Finally, we show that there can be at most one vertex with out-degree 0. For the sake of contradiction assume that u and v both have out-degree 0 and let g(u,v)=w. By Property (I), we then also have g(u,w)=w and g(v,w)=w. If w≠ u, this implies that u has out-degree at least 1 and if w≠ v, it implies that v has out-degree at least 1.

  Hence, G is a rooted tree on the set of labels of the labeling scheme. Because the ancestry relationship of G is consistent with the labeling scheme, G is an NCA-universal tree for the family 𝒯.



abbrv










§ APPENDIX



 §.§ Induction Basis


For n equals one through four it is simple to find a universal tree of size at most n^2. For example:



S_n' shall have size at most 2n^2. We want for any n a large tree S_n' with a marked leaf such that we can embed any tree on n vertices with a marked leaf with the nca-function commuting. Again as example and induction basis:




It is easy to check that ∀ T ∈ℬ_l and ∀ T' ∈ℬ_l' the NCA-query is equivalent to the NCA-query in S_l or S_l' ∀ l ∈{1,..  , 4} resp.



