{"ID":2890438,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.19139","arxiv_id":"2507.19139","title":"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 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.","short_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 objective is to find a new string that differs from each input string by at most...","url_abs":"https://arxiv.org/abs/2507.19139","url_pdf":"https://arxiv.org/pdf/2507.19139v2","authors":"[\"Estéban Gabory\",\"Laurent Bulteau\",\"Gabriele Fici\",\"Hilde Verbeek\"]","published":"2025-07-25T10:20:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}