  There are multiple factors which can cause the phylogenetic inference process
to produce two or more conflicting hypotheses of the evolutionary history of a
set X of biological entities. That is: phylogenetic trees with the same set of
leaf labels X but with distinct topologies. This leads naturally to the goal of
quantifying the difference between two such trees T_1 and T_2. Here we
introduce the problem of computing a 'maximum relaxed agreement forest' (MRAF)
and use this as a proxy for the dissimilarity of T_1 and T_2, which in this
article we assume to be unrooted binary phylogenetic trees. MRAF asks for a
partition of the leaf labels X into a minimum number of blocks S_1, S_2, ...
S_k such that for each i, the subtrees induced in T_1 and T_2 by S_i are
isomorphic up to suppression of degree-2 nodes and taking the labels X into
account. Unlike the earlier introduced maximum agreement forest (MAF) model,
the subtrees induced by the S_i are allowed to overlap. We prove that it is
NP-hard to compute MRAF, by reducing from the problem of partitioning a
permutation into a minimum number of monotonic subsequences (PIMS).
Furthermore, we show that MRAF has a polynomial time O(log n)-approximation
algorithm where n=|X| and permits exact algorithms with single-exponential
running time. When at least one of the two input trees has a caterpillar
topology, we prove that testing whether a MRAF has size at most k can be
answered in polynomial time when k is fixed. We also note that on two
caterpillars the approximability of MRAF is related to that of PIMS. Finally,
we establish a number of bounds on MRAF, compare its behaviour to MAF both in
theory and in an experimental setting and discuss a number of open problems.
