2025/07/25 by Estéban Gabory, Gabory, Estéban, Laurent Bulteau +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Genome Rearrangement Algorithms #Algorithms and Data Compression #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2507.19139
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 objective 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.