Algorithmic View on Circular String Attractors

Abstract

The notion of circular string attractor has been recently introduced by Mantaci et al. [TCS 2021]. It consists of a set Γ𝑐 of positions in a word such that each distinct circular factor has at least an occurrence crossing one of the elements of Γ𝑐. Its definition is an extension of the notion of string attractor by Kempa and Prezza [STOC 2018], which has been introduced as a unifying framework for some dictionary-based compressors. In this paper, we present the first linear time algorithm to check whether a set is a circular string attractor of a word 𝑤 ∈ {𝑎1, . . . , 𝑎𝜎}𝑛 by using 𝑂(𝑛 log 𝑛) bits of space. We further show that, for each 𝑝 > 0, the decision problem of having a circular string attractor of size ≤ 𝑝 is NP-complete. The proof is obtained through a reduction from the analogous problem for string attractors, for which Kempa and Prezza [STOC 2018] proved the NP-completeness. This reduction naturally leads to a new algorithm for checking whether a set is a string attractor that, unlike one of the solutions proposed by Kempa et al. [ESA 2018], it is independent from the size of the alphabet.