In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set S of strings and a multiset M of symbols, and we look for an ordering Mo of M such that the number of input strings which are substrings of Mo is maximized. In SRCS we are given a set S of strings and a text T, and we look for a swap ordering To of T (an ordering of T obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of To is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter l). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless NP ⊆ coNP/Poly. Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to 10) or are over a binary alphabet.

Bonizzoni, P., Dondi, R., Mauri, G., Zoppis, I. (2015). Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective. ALGORITHMICA, 72(4), 914-939 [10.1007/s00453-014-9882-8].

### Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective

#### Abstract

In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set S of strings and a multiset M of symbols, and we look for an ordering Mo of M such that the number of input strings which are substrings of Mo is maximized. In SRCS we are given a set S of strings and a text T, and we look for a swap ordering To of T (an ordering of T obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of To is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter l). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless NP ⊆ coNP/Poly. Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to 10) or are over a binary alphabet.
##### Scheda breve Scheda completa Scheda completa (DC) Articolo in rivista - Articolo scientifico
Algorithms; APX-hardness; Parameterized complexity; Shortest common superstring; String comparison;
English
5-mag-2014
2015
72
4
914
939
reserved
Bonizzoni, P., Dondi, R., Mauri, G., Zoppis, I. (2015). Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective. ALGORITHMICA, 72(4), 914-939 [10.1007/s00453-014-9882-8].
File in questo prodotto:
File
Bonizzoni2015_Article_RestrictedAndSwapCommonSuperst.pdf.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 970.73 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/52190`
• 2
• 1