# Why is the Greedy Conjecture so difficult?

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 ?

• One of the reasons might be that the known properties of the standard graph representations of the problem (such as the Monge and Triple inequalities) are provably not sufficient for a proof of the greedy conjecture. See, e.g., Laube, Weinard "Conditional inequalities and the shortest common superstring problem", and Weinard, Schnitger "On the greedy superstring conjecture". – Alex Golovnev Oct 1 '19 at 20:37
• @AlexGolovnev: Seems like a perfectly good answer to me! – Joshua Grochow Oct 5 '19 at 17:24
• @JoshuaGrochow: Thanks! I'll now extend it to an answer. – Alex Golovnev Oct 7 '19 at 21:02

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).