ECCC-Report TR98-071https://eccc.weizmann.ac.il/report/1998/071Comments and Revisions published for TR98-071en-usWed, 09 Dec 1998 13:43:50 +0200
Paper TR98-071
| The median problems for breakpoints are NP-complete |
Itsik Pe'er,
Ron Shamir
https://eccc.weizmann.ac.il/report/1998/071The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint distances to all the original ones. Recently, the
problem was suggested as a model for determining the evolutionary
history of several species based on their gene orders. We show
that the problem is already NP-hard for three permutations, and
that this result holds both for signed and for unsigned
permutations.
Wed, 09 Dec 1998 13:43:50 +0200https://eccc.weizmann.ac.il/report/1998/071