Superstrings with multiplicities

Eric Rivals 1, 2 Bastien Cazaux 1, 2
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas
Contributor : Eric Rivals <>
Submitted on : Wednesday, July 18, 2018 - 4:25:04 PM
Last modification on : Friday, March 15, 2019 - 1:15:12 AM
Long-term archiving on : Friday, October 19, 2018 - 9:38:47 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Eric Rivals, Bastien Cazaux. Superstrings with multiplicities. CPM: Combinatorial Pattern Matching, Qingdao University, Jul 2018, Qingdao, China. pp.21:1-21:16, ⟨10.4230/LIPIcs.CPM.2018.21⟩. ⟨lirmm-01843225⟩



Record views


Files downloads