@inbook{b7417698c87d41f1b069f9194da7ba7f,

title = "Finding the Anticover of a String",

abstract = "A k-anticover of a string x is a set of pairwise distinct factors of x of equal length k, such that every symbol of x is contained into an occurrence of at least one of those factors. The existence of a k-anticover can be seen as a notion of non-redundancy, which has application in computational biology, where they are associated with various non-regulatory mechanisms. In this paper we address the complexity of the problem of finding a k-anticover of a string x if it exists, showing that the decision problem is NP-complete on general strings for k-3. We also show that the problem admits a polynomial-time solution for k = 2. For unbounded k, we provide an exact exponential algorithm to find a k-anticover of a string of length n (or determine that none exists), which runs in O(min{3 n-k 3 , ( k(k+1) 2 ) n k+1 }) time using polynomial space. 2012 ACM Subject Classification Mathematics of computing ! Combinatorics on words.",

keywords = "Anticover, Np-complete, String algorithms, Stringology",

author = "Mai Alzamel and Alessio Conte and Shuhei Denzumi and Roberto Grossi and Iliopoulos, {Costas S.} and Kazuhiro Kurita and Kunihiro Wasa",

year = "2020",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.CPM.2020.2",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Gortz, {Inge Li} and Oren Weimann",

booktitle = "31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020",

address = "Germany",

note = "31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 ; Conference date: 17-06-2020 Through 19-06-2020",

}