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_i, j), where 1 <= i < j <= |u| and C_i, j is a subset of 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[l], respectively, then the induced gap v[k + 1..l - 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.