13
$\begingroup$

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 ?

$\endgroup$
  • 6
    $\begingroup$ 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". $\endgroup$ – Alex Golovnev Oct 1 at 20:37
  • $\begingroup$ @AlexGolovnev: Seems like a perfectly good answer to me! $\endgroup$ – Joshua Grochow Oct 5 at 17:24
  • $\begingroup$ @JoshuaGrochow: Thanks! I'll now extend it to an answer. $\endgroup$ – Alex Golovnev Oct 7 at 21:02
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.