Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds

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₈, ₉), where 1 <= i < j <= |u| and C₈, ₉ is a subset of A^*. Embedding u as a subsequence into v such that (i, j, C₈, ₉) is satisfied means that if ui and uj are mapped to vk and vl, respectively, then the induced gap vk + 1. . l - 1 must be a string from C₈, ₉. This generalises the setting recently investigated in Day et al. , ISAAC 2022, where only gap constraints of the form C₈, ₈ + ₁ are considered, as well as the setting from Kosche et al. , RP 2022, where only gap constraints of the form C₁, |ₔ| 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.