TY - CHAP
T1 - Finding the Anticover of a String
AU - Alzamel, Mai
AU - Conte, Alessio
AU - Denzumi, Shuhei
AU - Grossi, Roberto
AU - Iliopoulos, Costas S.
AU - Kurita, Kazuhiro
AU - Wasa, Kunihiro
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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.
AB - 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.
KW - Anticover
KW - Np-complete
KW - String algorithms
KW - Stringology
UR - http://www.scopus.com/inward/record.url?scp=85088393876&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2020.2
DO - 10.4230/LIPIcs.CPM.2020.2
M3 - Conference paper
AN - SCOPUS:85088393876
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
A2 - Gortz, Inge Li
A2 - Weimann, Oren
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
Y2 - 17 June 2020 through 19 June 2020
ER -