Pourquoi la conjecture gourmande est-elle si difficile?

J'ai récemment appris la conjecture gourmande du problème de chaîne la plus courte .

Dans ce problème, on nous donne un ensemble de chaînes $s_1,\dots, s_n$ et nous voulons trouver la chaîne la plus courte c'est-à-dire telle que chaque apparaisse comme une sous-chaîne de .$s$$s_i$$s$

Ce problème est NP-difficile et après une longue séquence d'articles, l'algorithme d'approximation le plus connu pour ce problème a un rapport [Paluch '14].$2+\frac{11}{30}$

En pratique, les biologistes utilisent l'algorithme Greedy suivant:

À chaque étape, fusionnez deux chaînes qui se chevauchent au maximum sur toutes les paires (le suffixe maximal qui est le préfixe d'une autre chaîne) et répétez sur cette nouvelle instance jusqu'à ce qu'il ne reste qu'une seule chaîne (qui est une super chaîne de toutes les chaînes d'entrée )

Une borne inférieure de dans le rapport d'approximation de cet algorithme gourmand peut être obtenue à partir de l'entrée .$2$$c(ab)^k,(ba)^k,(ab)^kc$

Fait intéressant, il a été conjecturé que c'est le pire exemple, c'est-à-dire que Greedy réalise une approximation de pour le problème de supercord le plus court. J'ai été très surpris de voir qu'un algorithme aussi naturel et facile est si difficile à analyser.$2$

Y a-t-il des intuitions, des faits, des observations, des exemples qui suggèrent pourquoi cette question est si difficile?

Permettez-moi d'abord d'essayer de résumer ce que l'on sait de la conjecture gourmande.

1. Blum, Jiang, Li, Tromp, Yannakakis prouvent que l'algorithme gourmand donne une approximation de 4, et Kaplan et Shafrir montrent qu'il donne une approximation de 3,5 pour le problème de supercord commun le plus court.
2. Une version de l'algorithme gourmand est connue pour donner une approximation 3 ( Blum, Jiang, Li, Tromp, Yannakakis ).
3. $3$$4$
4. La conjecture gourmande tient si l'algorithme gourmand fusionne des chaînes dans un ordre spécifique ( Weinard, Schnitger ; Laube, Weinard ).
5. L'algorithme glouton donne une approximation de 2 de la compression Tarhio, Ukkonen (qui est définie comme la longueur totale des chaînes d'entrée moins la longueur de la supertrusion commune la plus courte).
6. Il existe une implémentation extrêmement efficace de l'algorithme gourmand Ukkonen .

Je pense que l'une des raisons pour lesquelles il est difficile de prouver la conjecture gourmande pourrait être la suivante. La plupart des approches pour prouver les garanties d'approximation de l'algorithme glouton analysent le graphe de chevauchement (ou, de manière équivalente, le graphe de préfixe) de l'ensemble de chaînes d'entrée. Nous ne connaissons que certaines propriétés de ces graphiques (telles que les inégalités de Monge et de Triple), mais ces propriétés ne sont pas suffisantes pour prouver la conjecture gourmande ( Weinard, Schnitger ; Laube, Weinard ).