Why is the Greedy Conjecture so difficult?

Question

I recently learned about the Greedy conjecture for the Shortest Superstring Problem.

In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ i.e. such that each $s_i$ appears as a substring of $s$.

This problem is NP-hard and after a long sequence of papers the best known approximation algorithm for this problem has a ratio $2+\frac{11}{30}$ [Paluch '14].

In practice, biologists use the following Greedy algorithm:

At each step, merge two strings that has maximum overlap over all pairs (the maximum suffix that is the prefix of another string), and repeat on this new instance until there is only one string left (which is a superstring of the all input strings)

A lower bound of $2$ in the approximation ratio of this Greedy Algorithm can be obtained from the input $c(ab)^k,(ba)^k,(ab)^kc$.

Interestingly, it was conjectured that this is the worst example i.e. that Greedy achieves a $2$-approximation for Shortest Superstring Problem. I was very surprised to see that such a natural and easy algorithm is so difficult to analyse.

Are there any intuitions, facts, observations, examples that suggest why this question is that challenging ?

Answer 1

Let me first try to summarize what is known about the Greedy Conjecture.

1. Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
2. A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, Tromp, Yannakakis).
3. The Greedy Conjecture holds when all the input strings all of length at most $3$ (Tarhio, Ukkonen; Cazaux, Rivals) or $4$ (Kulikov, Savinov, Sluzhaev).
4. The Greedy Conjecture holds if the Greedy Algorithm happens to merge strings in some specific order (Weinard, Schnitger; Laube, Weinard).
5. The Greedy Algorithm gives a 2-approximation of the compression Tarhio, Ukkonen (which is defined as the total length of the input strings minus the length of the shortest common superstrting).
6. There is an extremely efficient implementation of the Greedy Algorithm Ukkonen.

I think that one of the reasons why it's hard to prove the Greedy Conjecture might be the following. Most of the approaches to proving approximation guarantees of the Greedy Algorithm analyze the overlap graph (or, equivalently, the prefix graph) of the input set of strings. We know only some properties of these graphs (such as Monge and Triple inequalities), but these properties are provably not sufficient for proving the Greedy Conjecture (Weinard, Schnitger; Laube, Weinard).