Por que a conjectura gananciosa é tão difícil?

Recentemente, aprendi sobre a conjectura gananciosa do menor problema das supercordas .

Nesse problema, recebemos um conjunto de seqüências de caracteres e queremos encontrar as menores supercordas ou seja, tais que cada apareça como uma subcadeia de .$s_1,\dots, s_n$ $s$$s_i$$s$

Esse problema é difícil para NP e, após uma longa sequência de trabalhos, o algoritmo de aproximação mais conhecido para esse problema possui uma proporção [Paluch '14].$2+\frac{11}{30}$

Na prática, os biólogos usam o seguinte algoritmo Greedy:

Em cada etapa, mescle duas cadeias que tenham sobreposição máxima em todos os pares (o sufixo máximo que é o prefixo de outra cadeia) e repita nesta nova instância até que exista apenas uma cadeia (que é uma supercadeia de todas as cadeias de entrada) )

Um limite inferior de na razão de aproximação deste algoritmo ganancioso pode ser obtido a partir da entrada .$2$$c(ab)^k,(ba)^k,(ab)^kc$

Curiosamente, foi conjeturado que este é o pior exemplo, ou seja, que Greedy alcança uma aproximação para o menor problema de supercorda. Fiquei muito surpreso ao ver que um algoritmo tão natural e fácil é tão difícil de analisar.$2$

Existem intuições, fatos, observações, exemplos que sugerem por que essa pergunta é tão desafiadora?

Deixe-me primeiro tentar resumir o que se sabe sobre a conjectura gananciosa.

1. Blum, Jiang, Li, Tromp, Yannakakis provam que o algoritmo ganancioso fornece uma aproximação de 4, e Kaplan e Shafrir mostram que ele fornece uma aproximação de 3,5 para o menor problema de supercorda comum.
2. Sabe-se que uma versão do algoritmo ganancioso fornece uma aproximação 3 ( Blum, Jiang, Li, Tromp, Yannakakis ).
3. A conjectura gananciosa é válida quando todas as cordas de entrada têm comprimento máximo de ( Tarhio, Ukkonen ; Cazaux, Rivals ) ou ( Kulikov, Savinov, Sluzhaev ).$3$$4$
4. A conjectura gananciosa se aplica se o algoritmo ganancioso mesclar seqüências de caracteres em alguma ordem específica ( Weinard, Schnitger ; Laube, Weinard ).
5. O algoritmo ganancioso fornece uma aproximação 2 da compressão Tarhio, Ukkonen (que é definida como o comprimento total das cadeias de entrada menos o comprimento da menor superestrela comum).
6. Existe uma implementação extremamente eficiente do algoritmo ganancioso Ukkonen .

Penso que uma das razões pelas quais é difícil provar a conjectura gananciosa pode ser a seguinte. A maioria das abordagens para provar as garantias de aproximação do algoritmo Greedy analisa o gráfico de sobreposição (ou, equivalentemente, o gráfico de prefixos) do conjunto de strings de entrada. Conhecemos apenas algumas propriedades desses gráficos (como as desigualdades de Monge e Triplo), mas essas propriedades provavelmente não são suficientes para provar a conjectura gananciosa ( Weinard, Schnitger ; Laube, Weinard ).