Maximum agreement subtree problem

The maximum agreement subtree problem is any of several closely related problems in graph theory and computer science.

In all of these problems one is given a collection of trees

The leaves of these trees are given labels from some set

so that no pair of leaves in the same tree sharing the same label, within the same tree the labelling for each leaf is distinct.

In this problem one would like to find the largest subset

such that the minimal spanning subtrees containing the leaves in

Source:[1] This version requires that the subtrees

This version is the same as the maximum homeomorphic agreement subtree, but we further assume that

This version of the maximum agreement subtree problem is used for the study of phylogenetic trees.

[1] Because of its close ties with phylogeny this formulation is often what is mean when one refers to the "maximum agreement subtree" problem.

There exits other formulations for example the (rooted) maximum isomorphic agreement subtree[1] where we require the subtrees to be isomorphic to one another.