Let \(\Sigma\) be an arbitrary set, which we call an alphabet. Denote by \(\Sigma^{*}\) the set of all finite tuples of elements of the alphabet \(\Sigma\). We call them strings or words. Denote by \(\Sigma^{+}\) the set of all strings over the alphabet \(\Sigma\) that does not contain the empty word \(\varepsilon\).
The shortest common superstring problem
A finite alphabet \(\Sigma\) and a set of strings \(U=\left\{ s_{1}, \ldots , s_{n}\right\} \subseteq \Sigma^{+}\).
A shortest common superstring \(s\), i.e., a string that contains every string \(s_{i}\) as a substring.
ExampleExample 1
Let \(U = \left\{ cbaa, abc, bcb\right\}\). Find a shortest common superstring.
SolutionSolution
A feasible solution: \(cbaabcb\)
An optimal solution: \(abcbaa\).
AnswerAnswer
\(abcbaa\).
If some string \(s\) in \(U\) is a substring of another string \(t\), then instead of \(U\) we can solve the problem for \(U' = U \setminus \left\{ s\right\}\). Clearly the optimal solution is the same for both problems. Hence, without loss of generality, we will henceforth assume that every string in \(U\) is βunique,β i.e., no string \(t\) contains another string \(s\) as a substring.
The shortest common superstring problem is \(NP\)-hard. We consider several approximation algorithms.
1 A greedy algorithm
Call the overlap\(\operatorname {ov}(s, t)\) of two strings \(s, t\) the longest string \(y\) such that \(s=x y\) and \(t=y z\) for some nonempty \(x, z\). Also let the prefix\(\operatorname {pr}(s, t)\) of the string \(s\) relative to \(t\) be the string \(x\) from the definition above. Thus \(s=\operatorname {pr}(s, t) \operatorname {ov}(s, t)\). Note that \(\operatorname {pr}(s, t) t\) is the shortest string containing \(s\) and \(t\) in that order. We call this string the merge of \(s\) and \(t\).
The following natural approach to the problem, called the greedy algorithm, works surprisingly well. We choose two strings \(s, t\) from \(U\) with the largest overlap and replace them by their merge. The algorithm stops when only one string remains, and clearly this string is a superstring of all the \(s_{i}\).
Algorithm 1Greedy algorithm for the shortest common superstring problem
a set of strings \(U = \{s_1, s_2, \ldots, s_n\}\).
a superstring \(s\) containing every string of \(U\) as a substring.
while\(|U| > 1\)do
Find two distinct strings \(s,t \in U\) for which the overlap length \(\operatorname{ov}(s,t)\) is maximal among all pairs of strings in \(U\).
Merge the strings \(s\) and \(t\) into a new string \[
r = \operatorname{pr}(s,t)t
\]
Remove the strings \(s\) and \(t\) from \(U\).
Remove from \(U\) every string that is a substring of \(r\).
Add \(r\) to \(U\).
Let \(s'\) be the single remaining string in \(U\).
return\(s'\)
ExampleExample 2
Let
\(U = \left\{ cbaa, abc, bcb\right\}\).
\(U = \left\{ a b^{k}, b^{k} c, b^{k+1}\right\}\), \(k \in \mathbb {N}\) Find a superstring using the greedy algorithm. Find a shortest common superstring. Compare them.
SolutionSolution
Enum-item(1)
Pairwise overlaps: \(\left|\operatorname {ov}(abc, bcb)\right| = 2\) (the string \(bc\)), \(\left|\operatorname {ov}(bcb, cbaa)\right| = 2\) (the string \(cb\)), all other overlaps have length \(0\) or \(1\). The greedy algorithm merges one of these pairs, say \(abc\) and \(bcb\) into \(abcb\); then \(\left|\operatorname {ov}(abcb, cbaa)\right| = 2\), and the merge gives \(abcbaa\) of length \(6\). Resolving the tie differently (\(bcb\) and \(cbaa \to bcbaa\), then merging with \(abc\)) gives the same string \(abcbaa\). Here the greedy algorithm found the shortest common superstring from the example above.
Enum-item(2)
All three maximal overlaps have length \(k\): \(\operatorname {ov}(a b^{k}, b^{k} c) = \operatorname {ov}(a b^{k}, b^{k+1}) = \operatorname {ov}(b^{k+1}, b^{k} c) = b^{k}\). If we first choose the first two strings, their merge \(a b^{k} c\) no longer overlaps with \(b^{k+1}\), and the greedy algorithm produces the string \(a b^{k} c b^{k+1}\) of length \(2k+3\), whereas the shortest common superstring \(a b^{k+1} c\) has length \(k + 3\). As \(k \to \infty\) the ratio tends to \(2\).
A bad example for the greedy string-merging algorithm
Three strings \(ab^{k}\), \(b^{k+1}\), \(b^{k}c\). On top: the optimal superstring \(ab^{k+1}c\) of length \(k+3\), where all three strings overlap. Below: the result of the greedy algorithm: the first maximal overlap (\(b^k\)) merges \(ab^k\) and \(b^kc\), after which the result no longer overlaps \(b^{k+1}\) β final length \(2k+3\). Hover over a bar to see which string is laid where.
4
Optimum:
Greedy algorithm:
As the example shows, the approximation ratio of the greedy algorithm is at least \(2\). There is an unproven conjecture:
Theorem 1 (The greedy algorithm conjecture) The greedy algorithm has approximation ratio \(2\).
The example above shows that the greedy algorithmβs ratio cannot be better than \(2\). From above, it has been rigorously proved that the ratio does not exceed \(4\) (Blum et al., 1991); Kaplan and Shafrir improved this bound to \(3.5\), and the best currently known bound is \(\approx 3.425\) (Englert et al., 2022).
2 An algorithm via set cover
2.1 Reduction to the set cover problem
2.1.1 Constructing the instance
Using the original set of strings \(U\) from the shortest common superstring problem, we construct a corresponding instance of the set cover problem, which we denote \(\mathcal{S}\). For each pair of strings \(s_{i}, s_{j} \in U\) and for some \(k \geq 1\), if the last \(k\) characters of the string \(s_{i}\) coincide with the first \(k\) characters of the string \(s_{j}\), we can construct a new string \(\sigma_{ijk}\) as the overlap-merge of \(s_{i}\) and \(s_{j}\) at \(k\) positions. Formally:
\[
\sigma _{ijk} = s_i[:-k] \; s_j
\]
(the first \(\left|s_i\right| - k\) characters of the string \(s_i\), followed by the entire string \(s_j\)).
For example, if \(s_i = \text{cabab}\) and \(s_j = \text{ababc}\), we get:
Here \(\sigma_{ij1}, \sigma_{ij3}, \ldots\) do not exist.
Each string \(\sigma_{ijk}\) corresponds to the set of original strings of \(U\) that it covers (i.e., that are substrings of it). We thus obtain an instance of the set cover problem: the set of all such \(\sigma_{ijk}\) covers the original set \(U\). Constructing an approximate solution to the superstring problem then reduces to finding a small subset of the strings \(\sigma_{ijk}\) that covers all the strings of \(U\).
Constructing the merge string \(\sigma_{ijk}\)
The last \(k\) characters of \(s_i\) match the first \(k\) characters of \(s_j\); the result of the merge \(\sigma_{ijk}=s_i[:-k]\,s_j\) is the whole string shown below. Move the slider: the larger the overlap, the shorter the merge.
3
Let the set \(\mathcal{F}\) consist of all possible admissible strings \(\sigma_{i j k}\). For each string \(\pi \in \Sigma^{+}\) define the set \(\operatorname {set}(\pi )=\{ s \in U \mid s\) is a substring of \(\pi \}\). We must cover the elements of \(U\) with the subsets \(\operatorname {set}(\pi )\), where \(\pi \in U \cup \mathcal{F}\). Set the weight of the set \(\operatorname {set}(\pi )\) equal to \(|\pi |\), i.e., the length of the string \(\pi\).
2.1.2 Accuracy of the reduction
Let \(\operatorname {OPT}_{\mathcal{S}}\) and \(\operatorname {OPT}\) denote the cost of an optimal solution of the cover instance \(\mathcal{S}\) and the length of the shortest common superstring, respectively. We show that these quantities can differ from each other by at most a factor of 2.
Consider an optimal cover \(\left\{ \operatorname {set}\left(\pi_{i}\right) \mid 1 \leq i \leq l\right\}\) and obtain a string \(s\) by concatenating the strings \(\pi_{i}, 1 \leq i \leq l\), in an arbitrary order. Clearly \(|s|=\operatorname {OPT}_{\mathcal{S}}\). Since every string of \(U\) is a substring of some string \(\pi_{i}\), it is also a substring of \(s\). Hence the resulting string is a superstring, and \(\operatorname {OPT}_{\mathcal{S}}=|s| \geq \operatorname {OPT}\).
To prove the second inequality, consider a shortest common superstring \(s^{*}\) for the strings \(s_{1}, \ldots , s_{n},\left|s^{*}\right|=\operatorname {OPT}\). We show that for the cover instance \(\mathcal{S}\) there exists a cover of weight at most \(2 \cdot \operatorname {OPT}\).
Consider the leftmost occurrence of the strings \(s_{1}, \ldots , s_{n}\) in the string \(s^{*}\). Since none of the strings \(s_{1}, \ldots , s_{n}\) is a substring of another, the leftmost occurrences of the \(n\) strings begin at distinct positions. For the same reason, they end at distinct positions. Renumber the strings in the order of their occurrence. Since none of the strings is a substring of another, they will also end in the same order.
Split the ordered list of strings \(s_{1}, \ldots , s_{n}\) into groups, as shown in the figure below. Each group will consist of a set of pairwise-overlapping strings. Denote by \(b_{i}\) and \(e_{i}\) the indices of the first and last string in the \(i\)-th group. If group \(i\) consists of a single string, then \(b_{i}=e_{i}\). Set \(b_{1}=1\). Let \(e_{1}\) be the largest index of a string overlapping with the string \(s_{1}\) (there is at least one such string β \(s_{1}\) itself). In general: if \(e_{i}<n\), set \(b_{i+1}=e_{i}+1\) and define \(e_{i+1}\) as the largest index of a string overlapping with the string \(s_{b_{i+1}}\). At the end of this process we get \(e_{t}=n\) for some \(t \leq n\).
Grouping the strings
The leftmost occurrences of strings \(s_1,\dots,s_n\) in the superstring \(s^{*}\), split into groups of pairwise-overlapping strings. \(s_{b_i}\) is the first (bold) string of group \(i\), \(s_{e_i}\) is the last; the segment \(\pi_i\) below is the merge \(\sigma_{b_ie_ik_i}\), starting at position \(b_i\) and ending at position \(e_i\). Hover over a group to highlight it and its corresponding \(\pi_i\).
For each pair of strings \(\left(s_{b_{i}}, s_{e_{i}}\right)\) there is some \(k_{i}>0\) giving the length of the overlap of these strings within the string \(s\) (which may differ from their maximal overlap). Let \(\pi_{i}=\sigma_{b_{i} e_{i} k_{i}}\). Then the collection of subsets \(\left\{ \operatorname {set}\left(\pi_{i}\right) \mid 1 \leq i \leq t\right\}\) is a feasible solution of the instance \(\mathcal{S}\), with cost \(\sum_{i}\left|\pi_{i}\right|\).
Now note that \(\pi_{i}\) does not overlap with \(\pi_{i+2}\). We prove this claim for \(i=1\). Suppose the strings \(\pi_{1}\) and \(\pi_{3}\) overlap. Then \(s_{b_{3}}\) overlaps with \(s_{e_{1}}\) in the string \(s^{*}\). However, by construction \(s_{b_{3}}\) does not overlap with \(s_{b_{2}}\) (since \(s_{b_{3}}\) belongs to the next group). Hence \(s_{e_{1}}\) ends later than \(s_{b_{2}}\). This contradicts the fact that the strings must end in the same order in which they begin. The proof for other values of \(i\) is analogous.
We thus find that each character of the string \(s^{*}\) belongs to at most two strings \(\pi_{i}\). From this we get \(\operatorname {OPT}_{\mathcal{S}} \leq \sum_{i}\left|\pi_{i}\right| \leq 2 \cdot \operatorname {OPT}\).
2.2 Applying set-cover algorithms
After the reduction, we can use some algorithm for the set cover problem. Consider, for example, applying the greedy algorithm.
Algorithm 2Building a superstring via the greedy set-cover algorithm
a set of strings \(U = \{s_1, s_2, \ldots, s_n\}\).
an approximate superstring \(s\) containing every string of \(U\) as a substring.
Over all pairs of strings in \(U\) and all admissible overlaps, build the strings \(\sigma_{ijk}\) and the family of sets \(\left\{\operatorname{set}(\pi) \mid \pi \in U \cup \mathcal{F}\right\}\) with weights \(\left|\pi\right|\).
Obtain an instance of the set cover problem: cover \(U\) with sets \(\operatorname{set}(\pi)\) of minimum total weight.
Using ChvΓ‘talβs greedy algorithm, find an approximate cover \(C = \{\operatorname{set}(\pi_{1}), \ldots, \operatorname{set}(\pi_{l})\}\).
Concatenate the strings \(\pi_{1}, \ldots, \pi_{l}\) in an arbitrary order, forming the superstring \(s = \pi_{1} \pi_{2} \ldots \pi_{l}\).
return\(s\)
The number of elements of \(U\) in the instance \(\mathcal{S}\) equals \(n\), i.e., the number of strings in the superstring problem.
Theorem 2 Algorithm @SSP:SetCov:GrAlg is a \(2 H_{n}\)-approximation algorithm for the superstring problem, where \(n\) is the number of strings in the given instance.
Mn-proofProof
The length of the constructed superstring equals \(\sum_{i=1}^{l} \left|\pi_i\right|\), i.e., the weight of the cover found. ChvΓ‘talβs greedy algorithm on a universe of \(n\) elements produces a cover of weight at most \(H_n \cdot \operatorname {OPT}_{\mathcal{S}}\), and by the reduction accuracy lemma \(\operatorname {OPT}_{\mathcal{S}} \leq 2 \cdot \operatorname {OPT}\). Altogether the length of the superstring does not exceed \(2 H_n \cdot \operatorname {OPT}\).