Resolviendo Superestring Exactamente

18

¿Qué se sabe sobre la complejidad exacta del problema de supercuerdas más corto? ¿Se puede resolver más rápido que O(2n) ? ¿Existen algoritmos conocidos que resuelvan la supercadena más corta sin reducir a TSP?

UPD: suprime los factores polinomiales.O()

El problema de la supercuerda más corta es un problema cuya respuesta es la cadena más corta que contiene cada cadena de un conjunto dado de cadenas. La pregunta es acerca de la extensión de optimización de un famoso problema NP-duro La Superstring más corta (Garey y Johnson, p.228).

Alex Golovnev
fuente
55
¿Qué es "el problema de la supercuerda"?
Jeffε
Me refería al problema de la supercuerda más corta, lo arreglé. ¡Gracias!
Alex Golovnev
10
Bien, entonces, ¿cuál es "el problema de supercuerdas más corto"? Puedo pensar en varios problemas que merecen ese nombre, y algunos más que deberían llamarse "el problema de supersecuencia más corto " pero que probablemente no están en la práctica. ¡Danos un poco de contexto, por favor!
Jeff el
1
¿Cuál es tu área problemática? por ejemplo, si busca la supercadena más corta en la fragmentación del genoma, debido a que la fragmentación del genoma crea gráficos de ancho de árbol acotado, puede tener un algoritmo rápido, pero si solo le interesan los algoritmos más rápidos que los disponibles, su respuesta es no, excepto que puede tener un algoritmo más rápido en TSP (debido a una reducción simple), también hay algoritmo en gráficos de ancho de árbol delimitados localmente. O(2n)
Saeed
1
@AlexGolovnev, Sí, tienes razón, esto es ATSP, pero para el ancho de árbol acotado creo que es bueno ver cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 o si quieres saber más sobre ellos también es bueno ver algoritmo meta teorema
Saeed

Respuestas:

5

Suponiendo que las cadenas tienen una longitud de polinomio en , entonces sí, hay al menos un 2 n - Ω ( nsolución de tiempo. La razón es la reducción bien conocida del problema de supercuerda común más corto a ATSP con pesos enteros de tamaño polinómico, que a su vez puede resolver mediante interpolación polinómica si puede contar los ciclos de Hamilton en un multigrafo dirigido. El último problema tiene un2n-Ω(2nΩ(n/logn)solución de tiempo. Björklund 20122nΩ(n/logn)

La reducción de ATSP con los pesos para cada par de vértices u , v para conteo ciclo de Hamilton va como sigue:wuvu,v

Para , donde w sum es un límite superior en todas las sumas de n pesos en la instancia ATSP, construya un gráfico G r donde reemplace cada peso w u v con r w u v arcos de u a v .r=1,2,,wsumwsumnGrwuvrwuvuv

Al resolver el conteo del ciclo hamiltoniano para cada , usted puede, mediante interpolación polinómica, construir un polinomio w suma l = 0 a l r l con una l igual al número de recorridos TSP en el gráfico original de peso l . Por lo tanto, localizar el l más pequeño de modo que un l no sea cero resuelve el problema.Grl=0wsumalrlalllal

Andreas Björklund
fuente
¡Muchas gracias! No conocía esta conexión con el conteo del ciclo hamiltoniano.
Alex Golovnev
@AlexGolovnev: ¿Pero la reducción es más o menos la misma que, por ejemplo, en el resultado de Kohn, Gottlieb, Kohn que citó en su propia respuesta? Es una incrustación simple de la suma de min-sum en los enteros. De todos modos, gracias por hacerme darme cuenta de que la próxima versión de mi artículo debería indicar esto explícitamente.
Andreas Björklund
8

He estudiado el problema y encontré algunos resultados. La Superstring común más corta (SCS) puede resolverse en el tiempo con solo espacio polinomial ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ).2n

La aproximación más conocida es (paluch).21130

La aproximación de compresión más conocida es (Paluch).34

Si SCS puede aproximarse por un factor sobre el alfabeto binario, entonces puede aproximarse por un factor α sobre cualquier alfabeto ( Vassilevska-Williams ).αα

SCS no se puede aproximar con una relación mejor que menos que P = NP ( Karpinski, Schmied ).1.0029

La compresión máxima no se puede aproximar con una relación mejor que menos que P = NP ( Karpinski, Schmied ).1.0048

Agradecería cualquier adición y sugerencia.

Alex Golovnev
fuente
5

Aquí está el problema de la supercadena más corta: se le dan cadenas s 1 , ... , s n sobre algún alfabeto Σ y desea encontrar la cadena más corta sobre Σ que contiene cada s i como una subsecuencia de caracteres consecutivos, es decir, una subcadena.ns1,,snΣΣsi

Cuando hablamos de algoritmos exactos para el problema, encontrar la longitud de la supercadena más corta es equivalente a encontrar la compresión máxima C, que es la suma de todas las superposiciones de cadenas consecutivas en la supercadena final, es decir, C = i | s i | - L .LCC=i|si|L

Hasta donde yo sé, el algoritmo exacto más rápido para las supercuerdas más cortas se ejecuta en ( 2 n ) donde n es el número de cadenas. Este es un algoritmo de programación dinámica simple similar al algoritmo de programación dinámica para la ruta más larga (y otros problemas):O2nn

Para cada subconjunto de cadenas y cadena v en S calculamos la compresión máxima sobre todas las supercadenas sobre S donde v es la primera cadena que aparece en la supercadena, almacenando esto como C (( v , S )). Hacemos esto procesando primero todos los subconjuntos con un solo elemento, y luego acumulando los valores de C (( v , S )) para los subconjuntos S en las cadenas k de aquellos en las cadenas k - 1 . Específicamente:SvSSvv,Sv,SSkk1

uSk1uu,uSvSuvv,S

n22n+n2l) where l is the maximum string length.

There are better algorithms if you assume that l is small, or the pairwise overlaps are small, the alphabet size is small etc, but I am not aware of any algorithm that's faster than 2n.

virgi
fuente
5
OP knows O(2n) algorithm, he asked for faster solution.
Saeed
2
as I said, I don't believe a faster solution is known.
virgi
1
@virgi, thank you very much! Your algorithm is very nice. But I think inclusion-exclusion principle gives us even O(2n)-algorithm with polynomial space for the Superstring problem. I'm really interesting in faster algorithms, may be with some constraints (small alphabet, short answer etc). Thank you very much!
Alex Golovnev