Sorting permutations by reversals and Eulerian cycle decompositions

We analyze the strong relationship among three combinatorial problems, name ly, the problem of sorting a permutation by the minimum number of reversals (MIN-SBR), the problem of finding the maximum number of edge-disjoint alte rnating cycles in a breakpoint graph associated with a given permutation (M AX-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 cha racterization 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 descr ibe a transformation from MAX-ACD to MIN-SBR, which is therefore shown to b e NP-hard as well, answering an outstanding question which has been open fo r 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 impli cations on approximation algorithms for MIN-SBR.