2026-07-24T06:07:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12127 2024-03-06T10:49:22Z ddc:004 open_access

Finding the Anticover of a String Alzamel, Mai Conte, Alessio Denzumi, Shuhei Grossi, Roberto Iliopoulos, Costas S. Kurita, Kazuhiro Wasa, Kunihiro Anticover String algorithms Stringology NP-complete 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mai Alzamel and Alessio Conte and Shuhei Denzumi and Roberto Grossi and Costas S. Iliopoulos and Kazuhiro Kurita and Kunihiro Wasa 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.2 urn:nbn:de:0030-drops-121270 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.2 eng https://creativecommons.org/licenses/by/3.0/legalcode