<p>Let me first try to summarize what is known about the Greedy Conjecture.</p>

<ol>
<li><a href="https://dl.acm.org/citation.cfm?id=179818" rel="noreferrer">Blum, Jiang, Li, Tromp, Yannakakis</a> prove that the Greedy Algorithm gives a 4-approximation, and <a href="https://www.sciencedirect.com/science/article/pii/S0020019004002698" rel="noreferrer">Kaplan and Shafrir</a> show that it gives a 3.5-approximation for the Shortest Common Superstring problem.</li>
<li>A version of the greedy algorithm is known to give a 3-approximation (<a href="https://dl.acm.org/citation.cfm?id=179818" rel="noreferrer">Blum, Jiang, Li, Tromp, Yannakakis</a>). </li>
<li>The Greedy Conjecture holds when all the input strings all of length at most <span class="math-container">$3$</span> (<a href="https://www.sciencedirect.com/science/article/pii/0304397588901673" rel="noreferrer">Tarhio, Ukkonen</a>; <a href="https://www.sciencedirect.com/science/article/pii/S0166218X1730183X" rel="noreferrer">Cazaux, Rivals</a>) or <span class="math-container">$4$</span> (<a href="https://link.springer.com/chapter/10.1007/978-3-319-19929-0_26" rel="noreferrer">Kulikov, Savinov, Sluzhaev</a>).</li>
<li>The Greedy Conjecture holds if the Greedy Algorithm happens to merge strings in some specific order (<a href="https://epubs.siam.org/doi/abs/10.1137/040619144" rel="noreferrer">Weinard, Schnitger</a>; <a href="https://www.worldscientific.com/doi/abs/10.1142/S0129054105003777" rel="noreferrer">Laube, Weinard</a>).</li>
<li>The Greedy Algorithm gives a 2-approximation of the compression <a href="https://www.sciencedirect.com/science/article/pii/0304397588901673" rel="noreferrer">Tarhio, Ukkonen</a> (which is defined as the total length of the input strings minus the length of the shortest common superstrting).</li>
<li>There is an extremely efficient implementation of the Greedy Algorithm <a href="https://link.springer.com/article/10.1007/BF01840391" rel="noreferrer">Ukkonen</a>.</li>
</ol>

<p>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 (<a href="https://epubs.siam.org/doi/abs/10.1137/040619144" rel="noreferrer">Weinard, Schnitger</a>; <a href="https://www.worldscientific.com/doi/abs/10.1142/S0129054105003777" rel="noreferrer">Laube, Weinard</a>).</p>

CC BY-SA 4.0
2019-10-07T21:02:58.673Z
2019-10-07T21:02:58.673Z
Alex Golovnev
<p>I recently learned about the Greedy conjecture for the <strong>Shortest Superstring Problem</strong>. </p>

<p>In this problem, we are given a set of strings <span class="math-container">$s_1,\dots, s_n$</span> and we want to find the <em>shortest superstring</em> <span class="math-container">$s$</span> i.e. such that each <span class="math-container">$s_i$</span> appears as a substring of <span class="math-container">$s$</span>. </p>

<p>This problem is NP-hard and after a long sequence of papers the best known approximation algorithm for this problem has a ratio <span class="math-container">$2+\frac{11}{30}$</span> [Paluch '14]. </p>

<p>In practice, biologists use the following Greedy algorithm:</p>

<p>At each step, merge two strings that has <em>maximum overlap</em> 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)</p>

<p>A lower bound of <span class="math-container">$2$</span> in the approximation ratio of this Greedy Algorithm can be obtained from the input <span class="math-container">$c(ab)^k,(ba)^k,(ab)^kc$</span>. </p>

<p>Interestingly, it was conjectured that this is the worst example i.e. that Greedy achieves a <span class="math-container">$2$</span>-approximation for Shortest Superstring Problem. I was very surprised to see that such a natural and easy algorithm is so difficult to analyse. </p>

<p><strong>Are there any intuitions, facts, observations, examples that suggest why this question is that challenging ?</strong></p>

CC BY-SA 4.0
2019-10-01T20:37:36.760Z
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
CC BY-SA 4.0
2019-10-05T17:24:43.277Z
@AlexGolovnev: Seems like a perfectly good answer to me!
Joshua Grochow
CC BY-SA 4.0
2019-10-07T21:02:30.750Z
@JoshuaGrochow: Thanks! I'll now extend it to an answer.
Alex Golovnev
<reference-request><approximation-algorithms><greedy-algorithms>
Why is the Greedy Conjecture so difficult?
Mathieu Mari
# Why is the Greedy Conjecture so difficult?

(Asked by: username_0 on 2019-10-01)

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 ?**

**Tags:** reference-request, approximation-algorithms, greedy-algorithms
> **Comments:**
> **username_1**: 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".  
> **username_2**: @AlexGolovnev: Seems like a perfectly good answer to me!  
> **username_1**: @JoshuaGrochow: Thanks! I'll now extend it to an answer.  

---

## 1 answers

### Answer by username_1 on 2019-10-07. Score: 10

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

1. [Blum, Jiang, Li, Tromp, Yannakakis](https://dl.acm.org/citation.cfm?id=179818) prove that the Greedy Algorithm gives a 4-approximation, and [Kaplan and Shafrir](https://www.sciencedirect.com/science/article/pii/S0020019004002698) 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](https://dl.acm.org/citation.cfm?id=179818)).
3. The Greedy Conjecture holds when all the input strings all of length at most $3$ ([Tarhio, Ukkonen](https://www.sciencedirect.com/science/article/pii/0304397588901673); [Cazaux, Rivals](https://www.sciencedirect.com/science/article/pii/S0166218X1730183X)) or $4$ ([Kulikov, Savinov, Sluzhaev](https://link.springer.com/chapter/10.1007/978-3-319-19929-0_26)).
4. The Greedy Conjecture holds if the Greedy Algorithm happens to merge strings in some specific order ([Weinard, Schnitger](https://epubs.siam.org/doi/abs/10.1137/040619144); [Laube, Weinard](https://www.worldscientific.com/doi/abs/10.1142/S0129054105003777)).
5. The Greedy Algorithm gives a 2-approximation of the compression [Tarhio, Ukkonen](https://www.sciencedirect.com/science/article/pii/0304397588901673) (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](https://link.springer.com/article/10.1007/BF01840391).

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](https://epubs.siam.org/doi/abs/10.1137/040619144); [Laube, Weinard](https://www.worldscientific.com/doi/abs/10.1142/S0129054105003777)).


---

