2026-09-05T06:57:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25940 2026-06-23T13:12:30Z ddc:004 open_access

Hardness Results on Characteristics for Elastic-Degenerate Strings Köppl, Dominik Olbrich, Jannik Elastic-degenerate strings NP-hardness longest common factor minimal unique substring minimal absent word anti-power longest previous factor Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al., 2022]. In that light, we wonder about other types of queries that are of particular interest to bioinformatics: unique substrings, absent words, anti-powers, longest previous factors, and Lempel-Ziv-like compression schemes. While we obtain a polynomial time algorithm for a variation of longest previous factors, we show that all other problems are NP-hard to compute, some of them even under the restriction that the input can be modeled as an indeterminate or GD string. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominik Köppl and Jannik Olbrich 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.14 urn:nbn:de:0030-drops-259409 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode