¿Qué se sabe sobre la complejidad exacta del problema de supercuerdas más corto? ¿Se puede resolver más rápido que ? ¿Existen algoritmos conocidos que resuelvan la supercadena más corta sin reducir a TSP?
UPD: suprime los factores polinomiales.
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).
cc.complexity-theory
ds.algorithms
graph-theory
tsp
exp-time-algorithms
Alex Golovnev
fuente
fuente
Respuestas:
Suponiendo que las cadenas tienen una longitud de polinomio en , entonces sí, hay al menos un 2 n - Ω ( √n solució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:wuv u,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,⋯,wsum wsum n Gr wuv rwuv u v
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.Gr ∑wsuml=0alrl al l l al
fuente
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.
fuente
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.n s1,…,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 .L C C=∑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):O∗ 2n n
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:S v S S v v,S v,S S k k−1
There are better algorithms if you assume thatl 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 .
fuente