Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
<|reference_start|>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.<|reference_end|>
@article{manea2024subsequences,
    title={Subsequences With Generalised Gap Constraints: Upper and Lower
  Complexity Bounds},
    author={Florin Manea, Jonas Richardsen, Markus L. Schmid},
    journal={arXiv preprint arXiv:2404.10497},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.10497},
    primaryClass={cs.DS}
}