String Consensus Problems with Swaps and Substitutions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913961859874816 |
|---|---|
| author | Gabory, Estéban Bulteau, Laurent Fici, Gabriele Verbeek, Hilde |
| author_facet | Gabory, Estéban Bulteau, Laurent Fici, Gabriele Verbeek, Hilde |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19139 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | String Consensus Problems with Swaps and Substitutions Gabory, Estéban Bulteau, Laurent Fici, Gabriele Verbeek, Hilde Data Structures and Algorithms Computational Complexity 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. |
| title | String Consensus Problems with Swaps and Substitutions |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2507.19139 |