String attractors: Verification and optimization

D. Kempa, A. Policriti, N. Prezza, E. Rotenberg

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set γ ⊆ [1.n] is a k-attractor for a string S ∈ Σn if and only if every distinct substring of S of length at most k has an occurrence crossing at least one of the positions in γ. Finding the smallest k-attractor is NP-hard for k ≥ 3, but polylogarithmic approximations can be found using reductions from dictionary compressors. It is easy to reduce the k-attractor problem to a set-cover instance where the string's positions are interpreted as sets of substrings. The main result of this paper is a much more powerful reduction based on the truncated suffix tree. Our new characterization of the problem leads to more efficient algorithms for string attractors: we show how to check the validity and minimality of a k-attractor in near-optimal time and how to quickly compute exact solutions. For example, we prove that a minimum 3-attractor can be found in O(n) time when |Σ| ∈ O(3+ϵ√log n) for some constant ϵ > 0, despite the problem being NP-hard for large Σ. © Dominik Kempa, Alberto Policriti, Nicola Prezza, and Eva Rotenberg.
Titel på gästpublikation26th Annual European Symposium on Algorithms (ESA 2018)
RedaktörerYossi Azar , Hannah Bast, Grzegorz Herman
Antal sidor13
FörlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroniskt)978-3-95977-081-1
StatusPublicerad - 2018
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangEuropean Symposium on Algorithms - Helsinki, Finland
Varaktighet: 20 aug 201822 aug 2018
Konferensnummer: 26


NamnLeibniz International Proceedings in Informatics (LIPIcs)
FörlagSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISSN (elektroniskt)1868-8969


  • 113 Data- och informationsvetenskap

Citera det här