License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.50
URN: urn:nbn:de:0030-drops-177026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17702/
Go to the corresponding LIPIcs Volume Portal

Olkowski, Jędrzej ; Pilipczuk, Michał ; Rychlicki, Mateusz ; Węgrzycki, Karol ; Zych-Pawlewicz, Anna

Dynamic Data Structures for Parameterized String Problems

pdf-format:
LIPIcs-STACS-2023-50.pdf (1 MB)

Abstract

We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a static algorithm that solves the given instance efficiently, our goal is to design a data structure that efficiently maintains a solution, or reports a lack thereof, upon updates in the instance.
We first consider the CLOSEST STRING problem, for which we design randomized dynamic data structures with amortized update times d^?(d) and |Σ|^?(d), respectively, where Σ is the alphabet and d is the assumed bound on the maximum distance. These are obtained by combining known static approaches to CLOSEST STRING with color-coding.
Next, we note that from a result of Frandsen et al. [J. ACM'97] one can easily infer a meta-theorem that provides dynamic data structures for parameterized string problems with worst-case update time of the form ?_k(log log n), where k is the parameter in question and n is the length of the string. We showcase the utility of this meta-theorem by giving such data structures for problems DISJOINT FACTORS and EDIT DISTANCE. We also give explicit data structures for these problems, with worst-case update times ?(k 2^k log log n) and ?(k²log log n), respectively. Finally, we discuss how a lower bound methodology introduced by Amarilli et al. [ICALP'21] can be used to show that obtaining update time ?(f(k)) for DISJOINT FACTORS and EDIT DISTANCE is unlikely already for a constant value of the parameter k.

BibTeX - Entry

@InProceedings{olkowski_et_al:LIPIcs.STACS.2023.50,
  author =	{Olkowski, J\k{e}drzej and Pilipczuk, Micha{\l} and Rychlicki, Mateusz and W\k{e}grzycki, Karol and Zych-Pawlewicz, Anna},
  title =	{{Dynamic Data Structures for Parameterized String Problems}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{50:1--50:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17702},
  URN =		{urn:nbn:de:0030-drops-177026},
  doi =		{10.4230/LIPIcs.STACS.2023.50},
  annote =	{Keywords: Parameterized algorithms, Dynamic data structures, String problems, Closest String, Edit Distance, Disjoint Factors, Predecessor problem}
}

Keywords: Parameterized algorithms, Dynamic data structures, String problems, Closest String, Edit Distance, Disjoint Factors, Predecessor problem
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI