OctoInformBeta

A factor-two approximation for shortest common superstring

A common superstring of a finite family 𝒮\mathcal S of finite words is a word containing every member of 𝒮\mathcal S as a contiguous substring. Write OPT⁡(𝒮)\operatorname{OPT}(\mathcal S) for the minimum length of such a word, measured in symbols. The input words are represented explicitly, including their encoded symbol labels and boundaries. Let NN be the total bit length of this representation. The shortest common superstring problem asks for a common superstring of minimum symbol length.

Tarhio and Ukkonen conjectured that the greedy maximum-overlap procedure attains factor 22. Blum, Jiang, Li, Tromp and Yannakakis gave the first polynomial-time constant-factor guarantee, 33, and later guarantees include 5/25/2 by Sweedyk, 2+11/232+11/23 by Mucha, (14+67)/9<2.466(14+\sqrt{67})/9<2.466 by Englert, Matsakis and Veselý, and 7/37/3 by Chukhin, Kulikov, Mihajlin and Smal.

The preprint proves that a deterministic algorithm, running in time polynomial in NN, returns a common superstring of symbol length at most 2OPT⁡(𝒮)2\operatorname{OPT}(\mathcal S) for every finite input family.

The Lean library Superstring treats ordinary strings whose symbols are bit strings. Its main theorem gives an algorithm AA such that, for every finite input family 𝒮\mathcal S, A(𝒮)A(\mathcal S) is a common superstring of length at most 2OPT⁡(𝒮)2\operatorname{OPT}(\mathcal S), and AA can be computed in time polynomial in NN by a machine over a finite alphabet.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.

The Lean library: Superstring

Superstring is a Lean library: 23 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): ordinary strings, explicit encoding and unrestricted optimum Symbol length and encoded input length. §1
  2. Theorem 1.1 A polynomial-time factor-two superstring algorithm. §1
§2. Forced occurrence counts 4 items
  1. §2 (setting): preprocessing, blocking and the count recursion Forced counts from finite substring data. §2
  2. Lemma 2.1 Forced counts give superstring lower bounds. §2
  3. §2 (setting): the hierarchical graph and base multiplicities Hierarchical walks and base edge multiplicities. §2
  4. Lemma 2.2 Forced counts balance the base edges. §2
§3. Periodic layers 6 items
  1. §3 (setting): periodic texts, actual windows and recorded occurrences Windows and occurrences in periodic layers. §3
  2. Lemma 3.1 Primitive layers preserve nonempty word counts. §3
  3. Lemma 3.2 Sorting periodic passages into ordered layers. §3
  4. Lemma 3.3 Counting blocked occurrences in periodic layers. §3
  5. Lemma 3.4 Distinct periodic texts have bounded agreement. §3
  6. Lemma 3.5 Early disagreement with a maximal forward rotation. §3
§4. Connection operations 4 items
  1. Lemma 4.1 Connecting ordered windows by hierarchical walks. §4
  2. Lemma 4.2 A bounded gap permits a band tour. §4
  3. Lemma 4.3 Linking bounded layers through a text window. §4
  4. Lemma 4.4 Connecting periodic layers through recorded windows. §4
§5. Processing the period groups 3 items
  1. §5 (setting): finite layer collections, records and plans Ordered periodic layers and their reserves. §5
  2. Lemma 5.1 Choosing sparse bands of periodic layers. §5
  3. Proposition 5.2 Period groups admit coverage within reserve. §5
§7. Polynomial time and the output string 1 item
  1. §7 (proof of Theorem 1.1): an executable complete tour and its bit complexity Computing a superstring within doubled weight. §7

No item matches.