On the hardness of the Consensus String problem

• We define the Consensus problem.
• We review results for the Euclidean metric and the Hamming string metric.
• We show that the Consensus String problem is NP-hard for the swap metric.
• We show that the Consensus String problem is APX-hard for the reversal metric.

Finding the consensus of a given set of strings is a hard and challenging problem. The problem is formally defined as follows: given a set of strings S={s1,…,sk} and a constant d, find, if it exists, a string s⁎ such that the distance of s⁎ from each of the strings does not exceed d.This problem has many applications. Two examples are: In biology, it may be used to seek a common ancestor to given sections of DNA. In web searching it may be used as a clustering aid.The stringology community researched this problem under the Hamming distance. In that metric the problem is NP-hard. A lot of work has been also done in the Euclidean metric.In this paper we consider the Consensus problem under other string metrics. We show that this problem is NP-hard for the swap metric and APX-hard for the reversal metric.