Abstract: The problem of the reversal distance between genomes on star-trees is discussed. It is proved that if the instance has 9 sequences given, the problem of the reversal distance on star-trees must be NP-hard. A polynomial approximation algorithm for the problem is given.