目标序列部分确定的翻转距离星树问题

A Problem of Reversal Distance on Star-Tree with Object Partially Fixed

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.

A problem of reversal distance on star-tree is discussed. The problem of 3SAT is induced to the problem of the reversal distance on star-tree with object partially fixed. The fact described below is proved: if an instance has 3 sequences given, and the order and some signs of the symbols in aimed sequence are fixed, it is still NP-hard to solve the problem of reversal distance on star-tree in which only need to decide the signs of the other symbols to minimizing the sum of distance between object and the given sequences. A polynomial approximation algorithm for the problem is given.