String Consensus Problems with Swaps and Substitutions

Abstract

String consensus problems aim at finding a string that minimizes some given distance with respect to an input set of strings. In particular, in the Closest String problem, we are given a set of strings of equal length and a radius d. The goal is to find a new string that differs from each input string by at most d substitutions. We study a generalization of this problem where, in addition to substitutions, swaps of adjacent characters are also permitted, each operation incurring a unit cost. Amir et al. showed that this generalized problem is NP-hard, even when only swaps are allowed. In this paper, we show that it is FPT with respect to the parameter d. Moreover, we investigate a variant in which the goal is to minimize the sum of distances from the output string to all input strings. For this version, we present a polynomial-time algorithm.