In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology as a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem has been considered too complex to derive mathematical models useful for its analysis and solution. We provide a powerful graph-theoretic relaxation of RMP, essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings. By using this relaxation, we can show the complexity of RMP as well as design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.
