Sorting Permutations by Reversals and Eulerian Cycle Decompositions

We analyze the strong relationship among three combinatorial problems, namely, the problem of sorting a permutation by the minimum number of reversals (MIN-SBR), the problem of finding the maximum number of edge-disjoint alternating cycles in a breakpoint graph associated with a given permutation (MAX-ACD), and the problem of partitioning the edge set of an Eulerian graph into the maximum number of cycles (MAX-ECD). We first illustrate a nice characterization of breakpoint graphs, which leads to a linear-time algorithm for their recognition. This characterization is used to prove that MAX-ECD and MAX-ACD are equivalent, showing the latter to be NP-hard. We then describe a transformation from MAX-ACD to MIN-SBR, which is therefore shown to be NP-hard as well, answering an outstanding question which has been open for some years. Finally, we derive the worst-case performance of a well-known lower bound for MIN-SBR, obtained by solving MAX-ACD, discussing its implications on approximation algorithms for MIN-SBR.