DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2024.22

Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds

Authors: Florin Manea, Jonas Richardsen, and Markus L. Schmid

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract

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.

Cite as

Florin Manea, Jonas Richardsen, and Markus L. Schmid. Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{manea_et_al:LIPIcs.CPM.2024.22,
  author =	{Manea, Florin and Richardsen, Jonas and Schmid, Markus L.},
  title =	{{Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.22},
  URN =		{urn:nbn:de:0030-drops-201329},
  doi =		{10.4230/LIPIcs.CPM.2024.22},
  annote =	{Keywords: String algorithms, subsequences with gap constraints, pattern matching, fine-grained complexity, conditional lower bounds, parameterised complexity}
}

Search Results

Documents authored by Richardsen, Jonas

Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds

Abstract

Cite as

Thanks for your feedback!

Could not send message