Resumen - Problemas de Consenso de Cadenas con Intercambios y Sustituciones

Problemas de Consenso de Cadenas con Intercambios y Sustituciones

2025-07-25 10:20:55

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

{cs.DS,cs.CC}

El documento investiga problemas de consenso de cadenas, específicamente enfocándose en el problema de la Cadena Más Cercana, donde el objetivo es encontrar una cadena que minimice una distancia dada (como la distancia de Hamming) en relación con un conjunto de entradas de cadenas. El documento extiende este problema permitiendo intercambios de caracteres adyacentes además de sustituciones, cada operación incurriendo en un costo unitario. Las contribuciones principales del documento son: 1. Los autores demuestran que el problema generalizado de encontrar una cadena que minimice la distancia máxima a todas las cadenas de entrada (con intercambios y sustituciones permitidas) es NP-difícil, incluso cuando solo se permiten intercambios. 2. Muestran que este problema es de parámetro tratable en tiempo polinomial (FPT) con respecto al parámetro d (la distancia máxima permitida). Esto significa que existe un algoritmo que se ejecuta en tiempo polinomial en función del tamaño de la entrada y exponencial en d. 3. Investigan una variante del problema donde el objetivo es minimizar la suma de distancias desde la cadena de salida a todas las cadenas de entrada. Presentan un algoritmo de tiempo polinomial para esta variante. El documento también considera la distancia de Intercambio, que es el número mínimo de intercambios necesarios para transformar una cadena en otra. Muestran que la variante de radio solo del problema de la Cadena Más Cercana bajo la distancia de Intercambio es FPT, y que la variante de suma solo está en P (tiempo polinomial). En resumen, el documento proporciona un análisis exhaustivo de los problemas de consenso de cadenas con intercambios y sustituciones y presenta algoritmos eficientes para resolver estos problemas.