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.