Before revision:  In particular, by plugging in the algorithm of Liu and Sidford [ArXiv 2019 ], we obtain an O(n^{ 11 / 8 }) time algorithm for computing the permutation distance between two trees on n nodes.
After revision:  In particular, by plugging in the algorithm of Liu and Sidford [ArXiv 2019 ], we obtain an O(n^{ 4 / 8 }) time algorithm for computing the permutation distance between two trees on n nodes.