¿Por qué es tan difícil la conjetura codiciosa?

Recientemente me enteré de la conjetura codiciosa para el problema de la supercuerda más corta .

En este problema, se nos da un conjunto de cadenas $s_1,\dots, s_n$ queremos encontrar la súper cadena más corta, $s$ decir, cada $s_i$ aparece como una subcadena de $s$ .

Este problema es NP-hard y después de una larga secuencia de documentos, el algoritmo de aproximación más conocido para este problema tiene una relación $2+\frac{11}{30}$ [Paluch '14].

En la práctica, los biólogos usan el siguiente algoritmo de Greedy:

En cada paso, combine dos cadenas que tengan una superposición máxima sobre todos los pares (el sufijo máximo que es el prefijo de otra cadena) y repita en esta nueva instancia hasta que solo quede una cadena (que es una supercadena de todas las cadenas de entrada )

Se puede obtener un límite inferior de $2$ en la relación de aproximación de este Algoritmo codicioso a partir de la entrada $c(ab)^k,(ba)^k,(ab)^kc$ .

Curiosamente, se conjeturó que este es el peor ejemplo, es decir, que Greedy logra una aproximación de $2$ para el problema de la supercuerda más corta. Me sorprendió mucho ver que un algoritmo tan natural y fácil es tan difícil de analizar.

¿Hay intuiciones, hechos, observaciones, ejemplos que sugieran por qué esta pregunta es tan desafiante?

Permítanme primero intentar resumir lo que se sabe sobre la Conjetura codiciosa.

1. Blum, Jiang, Li, Tromp, Yannakakis prueban que el Algoritmo codicioso da una aproximación de 4, y Kaplan y Shafrir muestran que da una aproximación de 3.5 para el problema de Superstring común más corto.
2. Se sabe que una versión del algoritmo codicioso da una aproximación de 3 ( Blum, Jiang, Li, Tromp, Yannakakis ).
3. $3$$4$
4. La Conjetura codiciosa se cumple si el Algoritmo codicioso fusiona cadenas en un orden específico ( Weinard, Schnitger ; Laube, Weinard ).
5. El Algoritmo codicioso proporciona una aproximación de 2 de la compresión Tarhio, Ukkonen (que se define como la longitud total de las cadenas de entrada menos la longitud de la superstrting común más corta).
6. Existe una implementación extremadamente eficiente del algoritmo codicioso Ukkonen .

Creo que una de las razones por las que es difícil probar la conjetura codiciosa podría ser la siguiente. La mayoría de los enfoques para probar las garantías de aproximación del algoritmo codicioso analizan el gráfico de superposición (o, equivalentemente, el gráfico de prefijo) del conjunto de cadenas de entrada. Solo conocemos algunas propiedades de estos gráficos (como las desigualdades de Monge y Triple), pero estas propiedades probablemente no sean suficientes para probar la conjetura codiciosa ( Weinard, Schnitger ; Laube, Weinard ).