  The last decade brought a significant increase in the amount of data and a
variety of new inference methods for reconstructing the detailed evolutionary
history of various cancers. This brings the need of designing efficient
procedures for comparing rooted trees representing the evolution of mutations
in tumor phylogenies. Bernardini et al. [CPM 2019] recently introduced a notion
of the rearrangement distance for fully-labelled trees motivated by this
necessity. This notion originates from two operations: one that permutes the
labels of the nodes, the other that affects the topology of the tree. Each
operation alone defines a distance that can be computed in polynomial time,
while the actual rearrangement distance, that combines the two, was proven to
be NP-hard.
  We answer two open question left unanswered by the previous work. First, what
is the complexity of computing the permutation distance? Second, is there a
constant-factor approximation algorithm for estimating the rearrangement
distance between two arbitrary trees? We answer the first one by showing, via a
two-way reduction, that calculating the permutation distance between two trees
on $n$ nodes is equivalent, up to polylogarithmic factors, to finding the
largest cardinality matching in a sparse bipartite graph. In particular, by
plugging in the algorithm of Liu and Sidford [ArXiv 2020], we obtain an
$O(n^{4/3+o(1)})$ time algorithm for computing the permutation distance between
two trees on $n$ nodes. Then we answer the second question positively, and
design a linear-time constant-factor approximation algorithm that does not need
any assumption on the trees.
