Bastien Cazaux
email: bastien.cazaux@cs.helsinki.fi

Eric Rivals
email: rivals@lirmm.fr

Superstrings with multiplicities

Keywords: 2012 ACM Subject Classification Mathematics of computing → Discrete mathematics, Theory of computation → Approximation algorithms analysis greedy algorithm -approximation -overlap -cyclic cover -APX -subset system Digital Object Identifier 10, 4230/LIPIcs, CPM, 2018, 21

A superstring of a set of words P = {s 1 , . . . , s p } is a string that contains each word of P as substring. Given P , the well known Shortest Linear Superstring problem (SLS), asks for a shortest superstring of P . In a variant of SLS, called Multi-SLS, each word s i comes with an integer m(i), its multiplicity, that sets a constraint on its number of occurrences, and the goal is to find a shortest superstring that contains at least m(i) occurrences of s i . Multi-SLS generalizes SLS and is obviously as hard to solve, but it has been studied only in special cases (with words of length 2 or with a fixed number of words). The approximability of Multi-SLS in the general case remains open. Here, we study the approximability of Multi-SLS and that of the companion problem Multi-SCCS, which asks for a shortest cyclic cover instead of shortest superstring. First, we investigate the approximation of a greedy algorithm for maximizing the compression offered by a superstring or by a cyclic cover: the approximation ratio is 1/2 for Multi-SLS and 1 for Multi-SCCS. Then, we exhibit a linear time approximation algorithm, Concat-Greedy, and show it achieves a ratio of 4 regarding the superstring length. This demonstrates that for both measures Multi-SLS belongs to the class of APX problems.

Introduction

Given a set of p words P := {s 1 , s 2 , . . . , s p } over a finite alphabet Σ, a superstring of P is a string containing each s i for 1 ≤ i ≤ p as a substring. The Shortest Linear Superstring (SLS) problem is an optimization problem that asks for a superstring of P of minimal length. It is also known as the Shortet Common Superstring problem, which does not convey the fact that the output superstring is a linear rather than cyclic word. SLS has been studied in depth for its applications in data compression, where a superstring is an alternative representation of P , and in bioinformatics [START_REF] Theodoros | Optimization in Science and Engineering[END_REF]. SLS is known to be hard to solve (NP-hard provided the input words are of length at least three) and to approximate (MAX-SNP-hard), and these difficulties remain even if one considers instances over a binary alphabet [START_REF] Gallant | On finding minimal length superstrings[END_REF][START_REF] Blum | Linear approximation of shortest superstrings[END_REF]17]. In bioinformatics, SLS models the initial step of genome assembly in a shotgun sequencing approach [START_REF] Anson | Algorithms for whole genome shotgun sequencing[END_REF], whose input is a large and redundant set of "reads". This first step consists in merging overlapping words to obtain partial substrings of the target genome. These output strings are called contigs. In practice, one never obtains a single superstring covering the genome, but a large set of contigs. A major difficulty that is inherent to biology comes from the presence of repeated regions in genomes. When assembled, the distinct copies of a repeat tend to collapse into a single occurrence, and the corresponding contig then exhibits a higher density of merged words [START_REF] Anson | Algorithms for whole genome shotgun sequencing[END_REF]. By comparing the local density of a contig to the expected density, one can estimate the underlying number of copies for a repeat. The assembly process can then be rerun using these multiplicities, that is for each word, the number of times it must appear in the superstring. To take into account the issue of repeated regions in SLS, Crochemore et al. have proposed a variant of SLS called Multi-SLS1 : the input consists in P with a function m giving the multiplicity of each word of P , and the output multi superstring must contain at least m(s i ) occurrences of s i , for any 1 ≤ i ≤ p [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF]. They present two polynomial time algorithms to solve two special cases of Multi-SLS: First, the case where the number of input words is constant, and second the case where each input word has length 2. The latter generalizes SLS for words of length 2, which can also be solved in polynomial time [START_REF] Gallant | On finding minimal length superstrings[END_REF].

Contributions

To our knowledge, the approximability of Multi-SLS in the general case (i.e., with an unbounded number of words of length ≥ 2) is wide open. As for SLS, two measures can be considered: the superstring length or its compression -the superstring length minus the sum of the lengths of all required occurrences of words of P . In general, for an optimization problem P, we denote by P comp the related problem that maximizes the compression measure.

Example 1. Consider the instance (P, m) with P := {aab, abaa, baba} with multiplicities m(aab) = 2, m(abaa) = 1, and m(baba) = 2. Then w := aabaabababa is a multi superstring of (P, m), it has length 11 and achieves of compression of 9 symbols. Similarly, the string y := aabaababaababababa, which results from concatenating the required words, also is a multi superstring of (P, m) of length 18 and thus yields a compression of 0.

In Section 3, we study the greedy algorithm for Multi-SLS comp and show it has a compression ratio of 1/2 in Theorem 9. In Section 5, we propose for Multi-SLS the first polynomial time approximation algorithm, called Concat-Greedy, and prove in Theorem 15 that it admits an approximation ratio of 4 for the superstring length measure. Hence, we demonstrate:

Theorem 2. Both Multi-SLS and Multi-SLS comp belong to the class APX.

In fact, the ratio of 4 follows from a stronger bound on the length of a solution of Concat-Greedy (see Proposition 14 p. 12). Note that the same ratio of 4 was proven for the classical SLS problem by [START_REF] Blum | Linear approximation of shortest superstrings[END_REF] in 1994, using the Concat-Cycles algorithm. To achieve this bound, Concat-Greedy must solve a related problem called Multi-SCCS, where the solution is a set of cyclic strings that collectively contain all the required occurrences of words of P . Such a set is called a cyclic cover of strings, or cyclic cover for short. First, we show in Section 3 that a greedy algorithm solves exactly Multi-SCCS, and then exhibit in Section 4 a graph based algorithm for it and bound its time complexity, which yields: Theorem 3. The Multi-Greedy algorithm (Algo. 2) solves the Multi-SCCS problem in a time that is linear in the size of its output.

Preliminaries

Here, we introduce basic notions on strings, permutations, superstrings and formally define the two problems Multi-SLS and Multi-SCCS. Then, we derive a logical, but important fact: all multi superstrings (resp. multi cyclic cover) we need to consider are induced by permutations. For any finite set U , |U | denotes its cardinality.

About strings Let u, v be two linear strings. We denote by |u| the length of u, and by uv their concatenation. Given a linear string u, we obtain the circular string u by linking the last letter of the linear string u to its first letter. The length of the circular string u is the length of the linear string u. Given a set of linear or circular strings P , we call the norm of P , denoted by ||P ||, i.e. the sum of the lengths of the strings of P . Let x := x 1 . . . x n and y := y 1 . . . y m be two linear strings (where for any 1 ≤ j ≤ m, y j is the j th letter of y). We denote by Occ(y, x) the set of the occurences of y in x, i.e., the set of positions i between 1 and n -m + 1 such that x i . . . x i+m-1 = y 1 . . . y m . Whenever Occ(y, x) is not empty, y is said to be a substring of x. We extend the notion of substring to circular strings by extending the set of occurences: we denote by Occ(y, x ) the set Occ(y, x ∞ ) ∩ {1, . . . , |x|} (where x ∞ = xx . . .). A prefix y (respectively a suffix) of a linear string x is a substring beginning (respectively ending) x, i.e., 1 ∈ Occ(y, x) (resp. |x| -|y| + 1 ∈ Occ(y, x)). Furthermore, we say that y is a proper substring of x if |y| < |x| (Definitions of a proper prefix/suffix are similar). Let M be a set of linear or circular strings; we denote by Occ(x, M ) the set of all occurences of x in all strings of M .

Problem definitions Throughout the article, let P := {s 1 , . . . , s p } be a set of linear strings P and a function m from P to N * giving the multiplicity of each string. We assume that P is factor-free, i.e., s i is not a substring of s j for any i, j in {1, . . . , p}. The pair (P, m) is the input of the problems Multi-SLS and Multi-SCCS. A superstring of P is a word w such that for any 1

≤ i ≤ p, |Occ(s i , w)| ≥ 1.
Let us define formally the two minimization problems Multi-SLS and Multi-SCCS: both seek to minimize their output length. Note that Definition 4 is equivalent to that MULTI-SCS(k) from [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF].

Definition 4 (Multi Shortest Linear Superstring (Multi-SLS)). Let P := {s 1 , . . . , s p } be a set of strings and m a function from P to N * . It seeks a linear string w of minimal length and such that for all s i ∈ P , |Occ(s i , w)| ≥ m(s i ).

Definition 5 (Multi Shortest Cyclic Cover of Strings (Multi-SCCS)). Let P := {s 1 , . . . , s p } be a set of strings and m a function from P to N * . It seeks a set C of circular strings of minimal norm and such that for all

s i ∈ P , |Occ(s i , C)| ≥ m(s i ).
In any solution of Multi-SLS or of Multi-SCCS, each string s of P must occur at least m(s) times. Let us define P to be the set containing m(s) copies of each word s of P ; to C P M 2 0 1 8 aab, 1 aab, 2 aab, 3 abaa, 1 abaa, 2 ababb, 1 abba, 1 abba, 2 abba, 3 aab abaa ababb abba distinguish its copies we denote any element of P by a pair (s, i) for 1 ≤ i ≤ m(s) -see Example 6 and Figure 1. Formally, i.e.

P = s∈P ∪ m(s) i=1 {(s, i)} .
For an element (s, i) of P , we denote by word((s, i)) the word s of P , i.e., word((s, i)) = s.

Note that for some instances -when words of P do not overlap each other -an optimal solution for Multi-SLS is the concatenation of all strings in P , and has length || P || := p i=1 m(s i ) |s i |. This observation remains valid for Multi-SCCS. Any algorithm solving Multi-SLS or Multi-SCCS has its complexity bounded by the length of its output, i.e., by || P ||, which we consider to be linear in the input size. In [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF], the authors seek to find a compressed representation of the output; we dwell on this question on page 11.

Example 6 (see Figure 1). This same instance (P, m) is used as running example throughout the paper. Let P = {aab, abaa, ababb, abba} be a set of strings and m be the function from P to N * such that m(aab) = 3, m(abaa) = 2, m(ababb) = 1 and m(abba) = 3. We have that P = {(aab, 1), (abb, 2), (abb, 3), (abaa, 1), (abaa, 2), (ababb, 1), (abba, 1), (abba, 2), (abba, 3)}.

About permutations Given a permutation σ of a set E, a successor y of an element x of E by σ, is an element of E such that y = σ k (x) where σ 1 (x) = σ(x) and σ k (x) = σ k-1 (σ(x)). We denote by Part(E, σ) the partition {E 1 , . . . , E p } of E where each element of E and its successors are in the same subset E i . A permutation is said circular if all the elements of E are successors of any element of E, i.e. Part(E, σ) = {E}. Moreover, we denote by Decomp(E, σ) the decomposition into circular permutations of the permutation σ, i.e., the set of pairs (E i , σ i ) where E i ∈ Part(E, σ) and where σ i is the restriction of σ to the elements of E i .

About linear and circular superstrings

Given two linear strings u and v, an overlap from u over v is a linear string that is a proper suffix of u and a proper prefix of v. We denote by ov(u, v) the longest overlap from u to v (also termed maximal overlap). Overlaps are not symmetrical. The prefix from u to v, denoted by pr(u, v) is the string satisfying u = pr(u, v)ov (u, v). The merge from u to v is the linear string pr(u, v)v if u = v, and the circular string pr(u, u) otherwise. Given a set of strings P , we denote by Ov(P ) the set of all the maximal overlaps between any two strings of P .

Let P = {s 1 , . . . , s p } be a set of linear strings. We denote by Linear(s 1 , . . . , s p ) (resp. by Circular(s 1 , . . . , s p )) the linear (resp. circular) string defined by the merge of s 1 , . . . , s p in this order: Linear(s 1 , . . . , s p ) := pr(s 1 , s 2 )pr(s 2 , s 3 ) . . . pr(s p-1 , s p )s p and Circular(s 1 , . . . , s p ) := pr(s 1 , s 2 )pr(s 2 , s 3 ) . . . pr(s p-1 , s p )pr(s p , s 1 ) .

Remark. The starting point of the merge does not impact Circular(). Formally, for all j ∈ {1, . . . , p}, Circular(s 1 , . . . , s p ) = Circular(s j , . . . , s p , s 1 , . . . , s j-1 ).

About multi superstrings and multi cyclic covers induced by a permutation

The number of possible superstrings or cyclic covers of P is infinite, which makes the search space for Multi-SLS / Multi-SCCS unpractical. Hence, a crucial issue is whether we can restrict this search space. For this sake, we introduce the notion of multi superstring/cyclic cover induced by a permutation.

Let τ be a permutation of P . If τ is a circular permutation (meaning that all its elements are successors of each other), we can define the multi superstring induced by τ and by an element s of P as follows:

Lin( P , τ, s) = Linear(next_word( s, 1), . . . , next_word( s, | P |))
where next_word( s, k) = word(τ k ( s)). Here, the term Linear() of this equation is the merge of the words of P in the order given by τ and ending with the chosen element s (indeed, next_word( s,

| P |) = word( s)).
In general, τ is not circular. It can be decomposed in several circular permutations (see Fig. 2a); we denote its decomposition by Decomp( P , τ ). We define, CC( P , τ ), the multi cyclic cover of strings induced by τ as follows:

CC( P , τ ) = ( Pi,σi)∈Decomp( P ,τ ) {Circular(next_word( s, 1), . . . , next_word( s, | P i |))}
where s is any element of P i and next_word( s, k) = word(σ k i ( s)). CC( P , τ ) is a set of cyclic strings, each obtained by merging the words in the order given by a sub-permutation σ i .

Example 7.

Let σ 1 and σ 2 be the permutations of P of Figure 2a and Figure 2b. Consider the pair (abba, 3) in P (node 3 in figures 2a and b); its direct successor with σ 1 is itself, i.e., σ 1 ((abba, 3)) = (abba, 3), and with σ 2 , it is the node 1 in Figure 2b, i.e., σ 2 ((abba, 3)) = (ababb, 1). Some thoughts lead to the observation that any optimal multi superstring or multi cyclic cover is necessarily induced by a permutation on P . This yields this proposition, which indeed restricts the search spaces of both problems. Due to space constraints, the proofs of some results (marked with a ) are not included here; some proofs are given in the appendix. Proposition 8 ( ). Let (P, m) be an instance of Multi-SLS and of Multi-SCCS. Let w opt be an optimal solution of Multi-SLS and let C opt be an optimal solution of Multi-SCCS. Then, there exist 1. a permutation τ of P such that C opt = CC( P , τ ). 2. a circular permutation ϕ of P and an element s of P such that w opt = Lin( P , ϕ, s).

Approximation

Here, let us define the greedy algorithms for Multi-SLS and Multi-SCCS problems and exhibit their approximation ratios for the measure of compression.

C P M 2 0 1 8 Greedy algorithms By Proposition 8, we have that each optimal solution of Multi-SCCS can be induced by a permutation on P . We can generalize the greedy algorithm for SCCS [START_REF] Cazaux | A linear time algorithm for Shortest Cyclic Cover of Strings[END_REF] to Multi-SCCS.

1 2 3 1 2 1 1 2 3 1 2 2 1 2 1 1 3 3 (a) Permutation σ1 of P 1 2 3 1 2 1 1 2 3 1 2 2 2 3 1 1 3
The basic principle of the greedy algorithm for SLS or SCCS is 1/ to merge a pair of strings at each step until all merge possibilities have been exhausted, and 2/ to consider pairs of strings to be merged in order of decreasing overlap length, and 3/ to break ties randomly. It is greedy because it chooses merge operations that yield the best compression first, and never backtracks on these choices. In fact, the greedy algorithm determines a total ordering on the merge operations (it is the greedy algorithm of a precise subset system -see [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF] for details). In stringology, the greedy algorithm is usually presented as in Algorithm 1: the initial set of words (set Q in Algorithm 1) is iteratively modified at each iteration of the main loop: a pair of strings is chosen, those strings removed from the set, and the string resulting from the merge is (re-)inserted in the set. The two formulations of the algorithm are equivalent [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF], basically because the new string offers the same overlaps with remaining words as the strings that were merged.

Of course the algorithm differs between the linear and cyclic cases. For SLS or Multi-SLS, the loop merges pairs of words until getting a single linear string, which is the final result. For SCCS or Multi-SCCS, the result is a set of cyclic strings, which is iteratively built (solution set S). A merge of two linear string results in a linear string, but the merge of a single string that self-overlaps yields a cyclic string. A cyclic string has no overlap and cannot be merged. Figure 3 Running set of all the Red-Blue graphs of (s, i) ∈ P for the permutation σ1 (see Figure 2a). A dashed arc (in red) links a string to its longest proper suffix, while a plain arc (in blue) links a longest proper prefix of a string to this string.

of s depends on Ov(P ): it may contain a suffix/prefix that is an overlap of another pair of words (∈ {(word( s), word(τ ( s))) | s ∈ P }). In Figure 3, it happens on the graph for the pair aab to abba since abb is not their maximal overlap. Let u and v be in P ∪ Ov(P ). By the definition of Red-Blue graphs, the arc linking u to v occurs only once in a given Red-Blue graph, i.e., |{(u, v)} ∩ (R ∪ B)| ∈ {0, 1} (see Lemma 16 in Appendix). We define NbOcc(τ, (u, v)) as the number of occurrences of the arc (u, v) in all Red-Blue graphs for all s in P . Thus, we get:

NbOcc(τ, (u, v)) := s ∈ P (V,R,B) = RB-Graph(τ, s) |{(u, v)} ∩ (R ∪ B)|.
Furthermore, we define PrefixArc(P ) (resp. SuffixArc(P )), as the set of arcs (u, v) (resp. (v, u)) of (P ∪ Ov(P )) 2 such that u is the longest prefix (resp. suffix) of v in P ∪ Ov(P ).

For a permutation τ of P that corresponds to a greedy solution for Multi-SCCS, we can count the NbOcc(τ, (u, v)) for all (u, v) ∈ PrefixArc(P ) ∪ SuffixArc(P ). For the sake of simplicity, we extend the function m to elements of Ov(P ) and set: m(w) = 0 for any w in Ov(P ).

Proposition 11. Let be τ ∈ GreedyPerm( P ) and (u, v) ∈ PrefixArc(P ) ∪ SuffixArc(P ). We have that

NbOcc(τ, (u, v)) = Max(m(v), -a(v)) if |u| ≤ |v| Max(m(u), a(u)) if |u| > |v|
where a(w) = elements of P and for permutation τ . Formally:

V = Ov(P ) \ U R = {(u, v) ∈ SuffixArc(P ) | NbOcc(τ, (u, v)) = 0} B = {(u, v) ∈ PrefixArc(P ) | NbOcc(τ, (u, v)) = 0} l : (u, v) → NbOcc(τ, (u, v))
where U = {v ∈ Ov(P ) | v is not an extremity of an arc of R ∪ B}. By Proposition 11, we have that for a permutation τ of GreedyPerm( P ) and (u, v) ∈ PrefixArc(P )∪SuffixArc(P ), the number of occurrences of the arc (u, v), i.e. NbOcc(τ, (u, v)), is independent of the permutation τ . From this observation and arguments from [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF], we deduce Proposition 12.

Proposition 12 ( ). Let τ 1 , τ 2 be two permutations of GreedyPerm( P ). Then, G p (τ 1 ) = G p (τ 2 ). By Proposition 12, all permutations inducing a greedy solution for an instance of Multi-SCCS yield the same graph, which we call the multi superstring graph and denote by SG(P, m) (see Figure 4b).

Using data structures like the (generalised) suffix tree to determine Ov(P ) [16], and with Proposition 11, we can build the multi superstring graph of (P, m) recursively and we obtain the following proposition.

Proposition 13 ( ). The multi superstring graph can be built in linear time and space in ||P ||.

Linear construction By Proposition 11, we know that for SG(P, m) = (V, R, B, l) the multi superstring graph of (P, m) the following equality holds:

∀v ∈ V, (v,u)∈R l((v, u)) - (u,v)∈B l((u, v)) = (u,v)∈R l((u, v)) - (v,u)∈B l((v, u)).
Hence, it follows that the multi superstring graph, in which the label of an arc is seen as a multi-arc, is Eulerian on each of its connected components. In Figure 4b, the arc from abba to a labelled by 3 means the Eulerian cycle must traverse this arc exactly thrice. Conversely, we can show that every set of cycles covering the multi superstring graph corresponds to a greedy solution for Multi-SCCS. As finding an Eulerian cycle cover of SG(P, m) takes a time linear in ||P ||, we deduce Theorem 3 (p. 3). Approximation algorithm for Multi-SLS Now, we propose an approximation algorithm for Multi-SLS and derive its approximation ratio with respect to the multi superstring length. By Theorem 9, we know that the greedy algorithm for Multi-SLS comp has an approximation ratio of 1/2, and thus it belongs to APX. Here, we extend the Concat-Cycles algorithm from [START_REF] Blum | Linear approximation of shortest superstrings[END_REF] and we show that this new algorithm, called Concat-Greedy, has an approximation ratio of 4 for Multi-SLS. The idea is to build an Eulerian multi-cycle of the multi superstring graph of (P, m), to break each cycle and merge its words to create linear strings, and to concatenate all these linear strings in an arbitrary order. Figure 5 displays an example of linearization.

To define formally the linearization of a cyclic cover of strings induced by permutation τ of P , we denote LinCC( P , τ, (w 1 , . . . , w p )) the following linearization LinCC( P , τ, (w 1 , . . . , w p )) = Lin( P 1 , σ 1 , w 1 ) . . . Lin( P p , σ p , w p ) where Decomp( P , τ ) = {( P 1 , σ 1 ), . . . , ( P p , σ p )} and (w 1 , . . . , w p ) ∈ P 1 × . . . × P p . Proposition 14 ( ). Let w CG be a solution of Algorithm 3, w OP T (Multi-SLS) be an optimal solution of Multi-SLS, and w OP T (SLS) be an optimal solution of SLS. We have:

|w CG | ≤ |w OP T (Multi-SLS) | + 3 × |w OP T (SLS) |.
As an optimal solution of Multi-SLS is longer than or equal to an optimal solution of SLS, one gets the following approximation ratio for Concat-Greedy, which is not tight.

Theorem 15. The approximation ratio of Algorithm Concat-Greedy for Multi-SLS is 4.

Remark. As we have made for

Multi-SCCS, we can compute a compact representation of Multi-SLS of size O(||P || × |P |) in time O(||P || 2 )
. Indeed, we linearize the compact representation of Multi-SCCS using Concat-Greedy to get a compact representation for Multi-SLS.

Conclusion

Here, we provide the first study of Multi-SLS in the general case, that is without restriction on the number of words, nor on the word length. Multi-SLS can be approximated for both the superstring length measure and for the compression measure. Finally, both Multi-SLS and Multi-SLS comp admit a constant approximation ratio, and thus belong to the class of APX problems. Proposition 14 shows that the difference in length between a multisuperstring returned by Concat-Greedy and an optimal multi-superstring is bounded by a term proportional to the length of an optimal superstring for SLS, on which the multiplicities have no impact. In practice, Concat-Greedy may produce solutions way below this bound. A future line of research is to implement this algorithm and evaluate its ratio experimentally, an approach of great interest for superstring problems. Indeed, for the classical SLS problem, a simple greedy like algorithm seems to yield superstrings very close to the optimum, achieving a ratio that is orders of magnitude smaller than the theoretical bound [START_REF] Cazaux | Practical lower and upper bounds for the shortest linear superstring[END_REF]. Indeed, experimental tests allow to compare approximation algorithms and may help pinpointing hard instances. Of course, the theoretical ratio of the greedy algorithm, and the best possible approximation ratio remain open questions for Multi-SLS.

Our main result regarding Multi-SCCS is its solvability in linear time. The Multi-Greedy algorithm paves the way to the design of new approximation algorithms for Multi-SLS, as was done for the classical SLS problem. Let us stress that even if our algorithm builds the multi superstring graph for (P, m), the multiplicities do not impact the numbers of nodes or of arcs, but only the weights on the arcs. As shown in Figure 4b, it is crucial that these numbers are independent of the multiplicities. Another issue is to understand what influences the number of cycles in a solution of Multi-SCCS; minimizing it may improve the output of Concat-Greedy, which "looses" some symbols each time it breaks a cycle.

Regarding future work, numerous variants of SLS (with reversals, with DNA strings [START_REF] Jiang | A note on shortest superstrings with flipping[END_REF][START_REF] Fici | On the greedy algorithm for the Shortest Common Superstring problem with reversals[END_REF]) or restrictions of SLS (e.g. to strings of the same length [START_REF] Cazaux | Relationship between superstring and compression measures: New insights on the greedy conjecture[END_REF]) can also be investigated with multiplicities. The question of updating a shortest superstring when the instance changes is challenging [START_REF] Bilò | Reoptimization of the shortest common superstring problem[END_REF]. Here, a change of multiplicity can be considered as an alteration of the instance.

A Details on the proofs for Theorems 9 and 10

This section summarizes the main lines of the proofs for Theorems 9 and 10 -formal proofs are left for a full version of this article. The proof of Theorem 9 (resp. Theorem 10) follows that of Theorem 3 (resp. Theorem 4) in [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF]. We refer the reader to [13] for details on subset systems and the notion of extendibility.

Both proofs rely on a subset system to analyze the greedy algorithm for solving Max-ATSP in general graphs, and on the proof of its approximation ratio on Overlap Graphs. The goal of Max-ATSP is to find a maximum weighted Hamiltonian path in a digraph G = (V, A). The subset system enforces three conditions on the arcs incorporated in a greedy solution: 1. any two arcs must start from distinct nodes 2. any two arcs must end in distinct nodes (i.e., the symmetrical of the first condition) 3. there exist no cycle of length smaller than the cardinality of V . These conditions ensure that the greedy algorithm indeed builds a Hamiltonian path. Thanks to its 3-extendibility and to Theorem 1 from [13], one deduce that the greedy algorithm yields a 1/3 approximation ratio for Max-ATSP, and similarly a 1/2 ratio for the Maximum Weighted Cycle Cover problem. However, these are the ratios for general graphs. In the case of overlap graphs, which satisfy the Monge condition [14], the proof of Theorem 3 in [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF] shows by analyzing finely the greedy approximation, that the greedy algorithm yields a 1/2 approximation ratio for Max-ATSP. Since, it is known that an approximation ratio for Max-ATSP translates directly to an approximation ratio for Maximum Compression [START_REF] Theodoros | Optimization in Science and Engineering[END_REF], which is the version of Shortest Linear Superstring that seeks to maximize compression measure, one gets a 1/2 approximation ratio for SLS. By applying this result on the overlap graph of P , one derives the 1/2 ratio for Multi-SLS comp . A similar proof ends up with an approximation ratio of 1 for the Maximum Weighted Cycle Cover problem on overlap graph. This yields the same ratio for Multi-SCCS comp , thereby showing that the greedy algorithm solves this problem exactly.

B Proof of Lemma 16 and Proposition 11

Lemma 16. Let τ be a permutation of P and s ∈ P . Consider RB-Graph(τ, s) := (V, R, B) be the Red-Blue graph of s, and let u and v be two strings of V . Then, the arc (u, v) occurs only once in the Red-Blue graph, in other words

|{(u, v)} ∩ (R ∪ B)| = 1.
Proof of Lemma 16. We face two alternatives: any arc belongs either to B or to R. By the definition of R, if (u, v) belongs to R, then v is the longest proper suffix of u in V . Thus, the length of u is strictly larger than that of v. By the definition of B, if (u, v) ∈ R, then u is the longest proper prefix of v in V . Thus, |u| < |v|. Hence, any arc of R ∪ B is either in R or in B, i.e., R ∩ B = ∅. By the unicity of the longest proper prefix/suffix, (u, v) cannot appear more than once in R nor in B, which concludes the proof.

Proof of Proposition 11. By definition,

NbOcc(τ, (u, v)) := s ∈ P (V,R,B)=RB-Graph(τ, s) |{(u, v)} ∩ (R ∪ B)|.
By Lemma 16, NbOcc(τ, (u, v)) is the number of times the arc (u, v) occurs in all Red-Blue graphs of all the elements of P .

To simplify the proof, we consider four alternative cases.

The case where u is an element of P . As P is factor-free, (u, v) is an arc of a Red-Blue graph (V, R, B), and (u, v) is an element of R (since |u| > |v|). Moreover, a(u) = 0 because the set {(w , w) ∈ SuffixArc(P )} ∪ {(w, w ) ∈ PrefixArc(P )} is empty. And thus, RB-graph(σ 2 , (s, i))

Figure 6 Running example: set of all the Red-Blue graphs of (s, i) ∈ P for the permutation σ2 (see Figure 2b).

Figure 1

 1 Figure 1 Example of P for the instance (P, m) of Example 6. Due to space constraints, for a pair of P we may write aab,2 or 2 .

1 ( 3 ( d )Figure 2

 13d2 abba, 3

( 3 ( a )Figure 4

 3a4 abba, 1 abba, 2

Figure 5 Algorithm 3 :

 53 Figure 5Running example: linearization LinCC( P , σ1, W ) of a cyclic cover of strings induced by permutation σ1 (see Figure2a) for W := abaa,1 , aab,2 , abba,2 , abba,1 , abba,3 .

  NbOcc(τ, (u, v)) = |{u | ∃k ∈ N, (u, k) ∈ P }| = m(u) = Max(m(u), a(u)).The case where v is an element of P . As P is factor-free, we get that (u, v) is an element of B since |u| < |v|, and that a(v) = 0. Hence,NbOcc(τ, (u, v)) = |{v | ∃k ∈ N, (v, k) ∈ P }| = m(v) = Max(m(v), -a(v)).The case where u / ∈ P , v / ∈ P and |u| < |v|. As |u| < |v|, the arc (u, v) is an element of B. As u / ∈ P and v / ∈ P , m(u) = m(v) = 0. NbOcc(τ, (u, v)) = |{ s ∈ P | (u, v) is an arc of RB-Graph(τ, s)}| = |{ s ∈ P | ov(word( s), word(τ ( s))) is a prefix of u}| = |{ s ∈ P | u is a proper prefix of word(τ ( s)), |ov(word( s), word(τ ( s)))| ≤ |u|}|.As τ is a permutation of GreedyPerm( P), and assuming that the set{ s ∈ P | u is a proper prefix of word(τ ( s)), |ov(word( s), word(τ ( s)))| ≤ |u|}is not empty (otherwise, we would have NbOcc(τ, (u, v)) = 0), we deduce thatNbOcc(τ, (u, v)) = |{ s ∈ P | u is a proper prefix of word(τ ( s))}| -|{ s ∈ P | u is a proper prefix of word(τ ( s)), |ov(word( s), word(τ ( s)))| = |v|}| -|{ s ∈ P | u is a proper prefix of word(τ ( s)), |ov(word( s), word(τ ( s)))| > |v|}| = (v,w)∈PrefixArc(P ) |{ s ∈ P | u and w are prefixes of word(τ ( s))}| -|{ s ∈ P | u and w are prefixes of word(τ ( s)), |ov(word( s), word(τ ( s)))| ≥ |w|}| -|{ s ∈ P | u is a proper prefix of word(τ ( s)), |ov(word( s), word(τ ( s)))| = |v|}| = (v,w)∈PrefixArc(P ) NbOcc(τ, (v, w)) -(w ,v)∈SuffixArc(P ) NbOcc(τ, (w v)). Hence, NbOcc(τ, (u, v)) = Max(m(v), -a(v)).

13

  Julián Mestre. Greedy in Approximation Algorithms. In Proceedings of 14th Annual European Symposium on Algorithms (ESA), volume 4168 of Lecture Notes in Computer Science, pages 528-539. Springer, 2006. 14 Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. In Mémoires de l'Académie Royale des Sciences, pages 666-704, 1781. 15 Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. Theoretical Computer Science, 57:131-145, 1988. 16 Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249-260, 1995. 17 Virginia Vassilevska. Explicit inapproximability bounds for the shortest superstring problem. In 30th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 3618 of Lecture Notes in Computer Science, pages 793-800. Springer, 2005.

2 0 1 8 21:16 Superstrings with multiplicities C Example: set of all Red-Blue graphs

  The case where u / ∈ P , v / ∈ P and |u| > |v| is similar to the previous case, where u / ∈ P , v / ∈ P and |u| < |v|. All cases have been considered and this concludes the proof.

	(s, i)	σ 2 ((s, i))
	aab, 1	abaa, 1	aab		ab		abaa
	aab, 2	abaa, 2	aab		ab		abaa
	aab, 3	abba, 2	aab	ab	abb		abba
	abaa, 1	aab, 2	abaa		aa		aab
	abaa, 2	aab, 3	abaa		aa		aab
	ababb, 1	abba, 1	ababb		abb		abba
	abba, 1	aab, 1	abba	a	aa		aab
	abba, 2	abba, 3	abba	a	ab	abb	abba
	abba, 3	ababb, 1	abba	a	ab		ababb

C P M

According to the notation of[START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF], this variant was termed MULTI-SCS.

Acknowledgements

We thank for the reviewers for their comments. 1

Funding This work is supported by the Institut de Biologie Computationnelle http://www. ibc-montpellier.fr (ANR-11-BINF-0002) and Défi MASTODONS C3G http://www.lirmm. fr/~rivals/C3G/ from CNRS.

Algorithm 1:

The greedy algorithm for Multi-SCCS.

1 Input: a pair (P, m); Output: S: a cyclic cover of strings covering P ; 2 S := ∅; // the solution set in construction 3 Q := P ; 4 newIndex := |Q|; 5 while |Q| > 0 do 6 (u, i) and (v, j) two elements of Q such that u and v have the longest overlap; // u can be equal to v and i equal to j 7 w is the merge of u and v; 11 return S Hence, each cyclic string is directly inserted into the solution set (set S, line 9), while a linear string is re-inserted in the set of strings remaining to be merged (set Q, line 10). This explains why the loop condition is |Q| > 0 (line 5).

Remark. Algorithm 1 is equivalent to iteratively merging the two elements u and v of P having the longest overlap, provided that u is not merged on its right 2 more than m(u) times and v is not merged on its left more than m(v) times. The word that results from the merge is inserted back into Q when it is linear, and inserted in the solution set S if it is cyclic. As elements of Q are pairs, we number each inserted word with a variable newIndex that is incremented on line 9.

We can also generalize the greedy algorithm for Multi-SCCS to Multi-SLS. To do so, we just need to change in Algorithm 1, the while condition "|Q| > 0" by "|Q| > 1" and, on line 6 "and i equal to j" by "but i cannot be equal to j".

Measure of compression

For the both problems Multi-SLS and Multi-SCCS, we want to minimize the length of the multi superstring or the norm of the multi cyclic cover of strings. If instead, we want to maximize the compression, that is the difference between the norm of P and the output size, we call the corresponding problems Multi-SLS comp and Multi-SCCS comp .

As the size of the input is constant, all optimal solutions of Multi-SCCS are also optimal solutions of Multi-SCCS comp , and vice versa. The set of optimal solutions of Multi-SLS is also equal to the set of optimal solutions of Multi-SLS comp . By Proposition 8, as we can restrict to solutions induced by a permutation of P , the compression can be seen as the sum of the lengths of the overlaps between two successive strings in the permutation. Indeed, for a permutation τ of P ,

where s ∈ P i and next_word( s, k) = word(σ k i ( s)). Similarly, we get that Multi-SLS comp 2 Merged on its right (resp. left) means using an overlap of its suffix (resp. prefix).

C P M 2 0 1 8

21:8

Superstrings with multiplicities maximizes the sum of the lengths of the successive overlaps in a multi superstring induced by a permutation.

Approximation for compression

We can see the greedy algorithm for SLS (and SLS comp ) as the greedy algorithm for finding a maximum weighted Hamiltonian path (Maximum Asymmetric Travelling Salesman Problem -Max-ATSP) in the overlap graph [15]. The overlap graph is a complete digraph labelled on the arcs, where each input word is a node, and where the length of the maximal overlap between two words is a weight on the corresponding arc [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Theorem 9 generalizes the half compression of greedy algorithm for SLS from [15] to Multi-SLS (full proof in the Appendix).

Theorem 9. The greedy algorithm for Multi-SLS comp has a 1 2 approximation ratio.

Proof. (See details in Appendix.) In [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF], we show that one can prove the approximation ratio of the greedy algorithm for SLS comp by combining the Monge inequality [14] with subset systems that simulate the greedy algorithm for Max-ATSP in graphs [13]. By building the overlap graph for P (see Figure 4a), we can use the same subset system on the maximal overlaps of P and obtain the same approximation ratio for the greedy algorithm of Multi-SLS comp as for that of SLS comp .

With the same arguments, we can show that the approximation ratio of the greedy algorithm for Multi-SCCS comp equals that of the greedy algorithm for SCCS comp , which is 1 [START_REF] Cazaux | The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings[END_REF]. This yields Theorem 10.

Theorem 10. For both problems Multi-SCCS comp and Multi-SCCS, the greedy algorithm (Algorithm 1) yields an optimal solution.

By Proposition 8 and by the fact that greedy solutions for Multi-SCCS are optimal, we can represent each greedy solution by a permutation of P . For any instance (P, m), let GreedyPerm( P ) denote the set of permutations of P corresponding to greedy solutions for Multi-SCCS.

Linear construction of Multi-SCCS

In this section, we show how to compute a greedy solution for Multi-SCCS in linear time in the norm of the set of strings of the input and in the norm of an optimal solution of Multi-SCCS. To achieve this, we adapt the superstring graph [START_REF] Cazaux | A linear time algorithm for Shortest Cyclic Cover of Strings[END_REF] in order to model greedy solutions for Multi-SCCS. Now, assume that one stores m(w), the multiplicity of a string w, in constant space (O(1) bits); hence the input, (P, m), has size O(||P ||).

Red-Blue graphs

To begin with, we define the Red-Blue graphs, which are intermediate digraphs needed to define the multi superstring graph -see Figure 3 (or Figure 6 in appendix).

Let τ be a permutation for P and s an element of P . We define, RB-Graph(τ, s) := (V, R, B), the Red-Blue graph of s for the permutation τ as V = {word( s), word(τ ( s))} ∪ {y ∈ Ov(P ) : |y| ≥ |ov(word( s), word(τ ( s)))| , and (y suffix of word( s) or y prefix of word(τ

By the properties of prefixes/suffixes, Red-Blue graphs are path graphs, which we illustrate in Figure 3 (running example and permutation σ 1 from Fig. 2a). Note that a Red-Blue graph Algorithm 2: The Multi-Greedy algorithm for Multi-SCCS 1 Input: a pair (P, m). Output: W a greedy solution for Multi-SCCS; 2 build SG(P, m) the multi superstring graph of (P, m); 3 compute an Eulerian multi-cycle c = (c 1 , . . . , c n ) of G P ; 4 for j ∈ [1, n] do 5 traverse c j : list the words of P whose node is in c j and insert the cyclic string of the concatenation of the corresponding prefixes in W ;

6 return W Compressed output representation At the beginning of this section, we have assumed that for each word of P , we can store the multiplicity in constant space. To improve the complexity, in this paragraph we assume that we can store the multiplicity of each string in O(||P ||) bits. In [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF], the authors present a compact representation of a solution for Multi-SLS with strings of length 2. They show that this compact representation has a size in O(||P || 2 ) and can be computed in O(||P || 2 ) time.

We can apply their technique to the multi superstring graph defined for Multi-SCCS. First, build the multi superstring graph of (P, m), and then using the algorithm EulerianCycle from [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF]