2026-07-20T04:49:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20132 2024-06-18T13:20:59Z ddc:004 open_access

Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds Manea, Florin Richardsen, Jonas Schmid, Markus L. String algorithms subsequences with gap constraints pattern matching fine-grained complexity conditional lower bounds parameterised complexity For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap constraint is a triple (i, j, C_{i, j}), where 1 ≤ i < j ≤ |u| and C_{i, j} ⊆ A^*. Embedding u as a subsequence into v such that (i, j, C_{i, j}) is satisfied means that if u[i] and u[j] are mapped to v[k] and v[𝓁], respectively, then the induced gap v[k + 1..𝓁 - 1] must be a string from C_{i, j}. This generalises the setting recently investigated in [Day et al., ISAAC 2022], where only gap constraints of the form C_{i, i + 1} are considered, as well as the setting from [Kosche et al., RP 2022], where only gap constraints of the form C_{1, |u|} are considered. We show that subsequence matching under generalised gap constraints is NP-hard, and we complement this general lower bound with a thorough (parameterised) complexity analysis. Moreover, we identify several efficiently solvable subclasses that result from restricting the interval structure induced by the generalised gap constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florin Manea and Jonas Richardsen and Markus L. Schmid 2024 Is Part Of LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2024.22 urn:nbn:de:0030-drops-201329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.22 eng https://creativecommons.org/licenses/by/4.0/legalcode