P. Flener, [BeldiceanuFlenerLorca06]

$\mathrm{𝚜𝚝𝚊𝚋𝚕𝚎}\_\mathrm{𝚌𝚘𝚖𝚙𝚊𝚝𝚒𝚋𝚒𝚕𝚒𝚝𝚢}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$

Figure 5.373.1 shows the two trees we want to merge. Note that the leaves $𝚊$ and $𝚏$ occur in both trees.

Figure 5.373.1. The two trees to merge

The left part of Figure 5.373.2 gives one way to merge the two previous trees. This solution corresponds to the ground instance provided by the example. Note that there exist 7 other ways to merge these two trees. They are respectively depicted by Figures 5.373.2 to 5.373.5.

Figure 5.373.2. First solution (corresponding to the ground instance of the example) and second solution on how to merge the two trees $T_1$ and $T_2$ of Figure 5.373.1

Figure 5.373.3. Third and fourth solutions on how to merge the two trees $T_1$ and $T_2$ of Figure 5.373.1

Figure 5.373.4. Fifth and sixth solutions on how to merge the two trees $T_1$ and $T_2$ of Figure 5.373.1

Figure 5.373.5. Seventh and eight solutions on how to merge the two trees $T_1$ and $T_2$ of Figure 5.373.1

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

One objective of phylogeny is to construct the genealogy of the species, called the tree of life, whose leaves represent the contemporary species and whose internal nodes represent extinct species that are not necessarily named. An important problem in phylogeny is the construction of a supertree [BinindaEmondsGittlemanSteel02] that is compatible with several given trees. There are several definitions of tree compatibility in the literature:

• A tree $𝒯$ is strongly compatible with a tree ${𝒯}^{\text{'}}$ if ${𝒯}^{\text{'}}$ is topologically equivalent to a subtree $𝒯$ that respects the node labelling. [NgWormald96]

• A tree $𝒯$ is weakly compatible with a tree ${𝒯}^{\text{'}}$ if ${𝒯}^{\text{'}}$ can be obtained from $𝒯$ by a series of arc contractions. [Steel92]

• A tree $𝒯$ is stably compatible with a set $𝒮$ of trees if $𝒯$ is weakly compatible with each tree in $𝒮$ and each internal node of $𝒯$ can be labelled by at least one corresponding internal node of some tree in $𝒮$.

For the supertree problem, strong and weak compatibility coincide if and only if all the given trees are binary [NgWormald96]. The existence of solutions is not lost when restricting weak compatibility to stable compatibility.

Figure 5.373.6. Supertree problem instance and two of its solutions

Figure 5.373.7. Three small phylogenetic trees

For example, the trees ${𝒯}_1$ and ${𝒯}_2$ of Figure 5.373.6 have $𝒯$ and ${𝒯}^{\text{'}}$ as supertrees under both weak and strong compatibility. As shown, all the internal nodes of ${𝒯}^{\text{'}}$ can be labelled by corresponding internal nodes of the two given trees, but this is not the case for the father of $b$ and $g$ in $𝒯$. Hence $𝒯$ and four other such supertrees are debatable because they speculate about the existence of extinct species that were not in any of the given trees. Consider also the three small trees in Figure 5.373.7: ${𝒯}_3$ and ${𝒯}_4$ have ${𝒯}_4$ as a supertree under weak compatibility, as it suffices to contract the arc $(3,2)$ to get ${𝒯}_3$ from ${𝒯}_4$. However, ${𝒯}_3$ and ${𝒯}_4$ have no supertree under strong compatibility, as the most recent common ancestor of $b$ and $c$, denoted by $\mathrm{𝑚𝑟𝑐𝑎}(b,c)$, is the same as $\mathrm{𝑚𝑟𝑐𝑎}(a,b)$ in ${𝒯}_3$, namely 1, but not the same in ${𝒯}_4$, as $\mathrm{𝑚𝑟𝑐𝑎}(b,c)=3$ is an evolutionary descendant of $\mathrm{𝑚𝑟𝑐𝑎}(a,b)=2$. Also, ${𝒯}_4$ and ${𝒯}_5$ have neither weakly nor strongly compatible supertrees.

Under strong compatibility, a first supertree algorithm was given in [AhoSagivSzymanskiUllman81], with an application for database management systems; it takes $O\left(l^2\right)$ time, where $l$ is the number of leaves in the given trees. Derived algorithms have emerged from phylogeny, for instance OneTree [NgWormald96]. The first constraint program was proposed in [GentProsserSmithWei03], using standard, non-global constraints. Under weak compatibility, a phylogenetic supertree algorithm can be found in [Steel92] for instance. Under stable compatibility, the algorithm from computational linguistics of [BodirskyKutz07] has supertree construction as special case.

root concept: $\mathrm{𝚝𝚛𝚎𝚎}$.

application area: bioinformatics, phylogeny.

constraint type: graph constraint.

final graph structure: tree.