Shortest Common Superstring
In the Shortest Common Superstring Problem (SCS), one is given a set of strings and needs to find the shortest string that contains all of them as substrings. We denote the set of $n$ input strings by $\mathcal{S}=\left\{s_1, \ldots, s_n\right\}$.
For a string $s$, by $|s|$ we denote its length. For non-empty strings $s$ and $t$, by $\text{ov}(s, t)$ we denote their overlap, that is, the longest string $y$, such that $s=xy$ and $t=yz$ for some non-empty strings $x$ and $z$. In this case, the string $xyz$ is called a merge of $s$ and $t$.
Example 1: Consider $\mathcal{S} = \{\texttt{abc}, \texttt{bcd}, \texttt{cde}\}$.
- $\text{ov}(\texttt{abc}, \texttt{bcd}) = \texttt{bc}$ (length 2)
- $\text{ov}(\texttt{bcd}, \texttt{cde}) = \texttt{cd}$ (length 2)
- Merging in order $(\texttt{abc}, \texttt{bcd}, \texttt{cde})$ gives: $\texttt{abcde}$ (length 5)
- Total length = $3 + 3 + 3 - 2 - 2 = 5$
Example 2: Consider $\mathcal{S} = \{\texttt{cat}, \texttt{atom}, \texttt{omit}\}$.
- $\text{ov}(\texttt{cat}, \texttt{atom}) = \texttt{at}$ (length 2)
- $\text{ov}(\texttt{atom}, \texttt{omit}) = \texttt{om}$ (length 2)
- Merging in order $(\texttt{cat}, \texttt{atom}, \texttt{omit})$ gives: $\texttt{catomit}$ (length 7)
- The compression is $2 + 2 = 4$
Example 3: Consider $\mathcal{S} = \{\texttt{ab}, \texttt{bc}, \texttt{ca}\}$.
- $\text{ov}(\texttt{ab}, \texttt{bc}) = \texttt{b}$, $\text{ov}(\texttt{bc}, \texttt{ca}) = \texttt{c}$, $\text{ov}(\texttt{ca}, \texttt{ab}) = \texttt{a}$
- Order $(\texttt{ca}, \texttt{ab}, \texttt{bc})$ gives: $\texttt{cabc}$ (length 4)
- Order $(\texttt{ab}, \texttt{bc}, \texttt{ca})$ gives: $\texttt{abca}$ (length 4)
Part A
Argue that to solve SCS, it is sufficient to find:
WLOG, there are no repeats. Any solution contains all the input strings in some order; this order corresponds to the desired permutation.
Part B
Observe that for a given $\pi$, the length of the corresponding superstring $s(\pi)$, which is obtained by writing the input strings in the order $\left(s_{\pi(1)}, \ldots, s_{\pi(n)}\right)$ and merging adjacent strings, is given by:
The compression of $\pi$ is the sum of the overlaps of adjacent strings in the permutation $\pi$. Finding a shortest superstring is equivalent to:
Since the sum of string lengths $\sum_{i=1}^n |s_i|$ is fixed, minimizing the superstring length is equivalent to maximizing the sum of overlaps (i.e., the compression).
Part C
Consider $\mathcal{S} = \{\texttt{abc}, \texttt{bca}, \texttt{cab}\}$. What is the length of the shortest common superstring?
Part D
We define an overlap graph $OG(\mathcal{S})$ associated with $\mathcal{S}$ as follows: $OG(\mathcal{S})$ is a complete directed graph $(V, E)$ (that is, for every $s, t \in V$ there are edges $(s, t)$ and $(t, s)$), where $V=\mathcal{S}$, and the weight of an edge $(s, t)$ is $|\text{ov}(s, t)|$.
Let us say that an edge $(u, v)$ dominates another edge $(u', v')$, if they share head or tail (that is, $u=u'$ or $v=v'$) and $|\text{ov}(u, v)| \geq |\text{ov}(u', v')|$.
In terms of the overlap graph, the greedy algorithm goes through a list of all edges in $OG(\mathcal{S})$ in the nonincreasing order of their overlap and includes some of them in a solution. Specifically, the greedy algorithm does not include another edge if and only if:
- R1. it is dominated by an already chosen edge,
- R2. it is not dominated but it would form a cycle.
What is the structure of the set of edges returned by the greedy algorithm?
The greedy algorithm selects exactly $n-1$ edges (one less than the number of vertices). By R1, each vertex has at most one outgoing and one incoming selected edge. By R2, there are no cycles. Together, this forms a Hamiltonian path.
Part E
Does the greedy algorithm always produce the optimal (shortest) superstring?
The greedy algorithm does not always produce the optimal solution. Consider $\mathcal{S} = \{\texttt{ab}, \texttt{bb}, \texttt{bc}\}$:
- Greedy might pick edge $(\texttt{ab}, \texttt{bb})$ with overlap 1, then $(\texttt{bb}, \texttt{bc})$ with overlap 1, giving $\texttt{abbc}$ (length 4).
- But the optimal is $(\texttt{ab}, \texttt{bc})$ with overlap 1, and $\texttt{bb}$ can overlap with both, giving potentially shorter solutions depending on the tie-breaking.
More generally, the greedy algorithm is known to give a 3.5-approximation for SCS.
Hints
Try different permutations and compute the overlaps for each adjacent pair.