Résumé - Problèmes de consensus des chaînes avec des échanges et des substitutions

Problèmes de consensus des chaînes avec des échanges et des substitutions

2025-07-25 10:20:55

{"Estéban Gabory","Laurent Bulteau","Gabriele Fici","Hilde Verbeek"}

{cs.DS,cs.CC}

L'article investigate les problèmes de consensus de chaînes, en se concentrant spécifiquement sur le problème de la Chaîne la plus proche, où l'objectif est de trouver une chaîne qui minimize une distance donnée (comme la distance de Hamming) par rapport à un ensemble d'entrée de chaînes. L'article étend ce problème en permettant des échanges de caractères adjacents en plus des substitutions, chaque opération entraînant un coût unitaire. Les contributions principales de l'article sont : 1. Les auteurs montrent que le problème généralisé de trouver une chaîne qui minimize la distance maximale à toutes les chaînes d'entrée (en autorisant les échanges et les substitutions) est NP-difficile, même lorsque seules les substitutions sont autorisées. 2. Ils démontreront que ce problème est tractable en paramètre (FPT) par rapport au paramètre d (la distance maximale autorisée). Cela signifie qu'il existe un algorithme qui s'exécute en temps polynominal par rapport à la taille de l'entrée et exponentiel en d. 3. Ils investiguent une variante du problème où l'objectif est de minimiser la somme des distances de la chaîne de sortie à toutes les chaînes d'entrée. Ils présentent un algorithme polynomial pour cette variante. L'article considère également la distance d'échange, qui est le nombre minimum d'échanges nécessaires pour transformer une chaîne en une autre. Ils montrent que la variante de la distance de la Chaîne la plus proche sous la distance d'échange est FPT, et que la variante de la somme est en P (temps polynominal). Dans l'ensemble, l'article fournit une analyse complète des problèmes de consensus de chaînes avec des échanges et des substitutions, et présente des algorithmes efficaces pour résoudre ces problèmes.