2026-07-22T16:00:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20121 2024-06-18T13:20:58Z ddc:004 open_access

Hairpin Completion Distance Lower Bound Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Fine-grained complexity Hairpin completion LCS Hairpin completion, derived from the hairpin formation observed in DNA biochemistry, is an operation applied to strings, particularly useful in DNA computing. Conceptually, a right hairpin completion operation transforms a string S into S⋅ S' where S' is the reverse complement of a prefix of S. Similarly, a left hairpin completion operation transforms a string S into S'⋅ S where S' is the reverse complement of a suffix of S. The hairpin completion distance from S to T is the minimum number of hairpin completion operations needed to transform S into T. Recently Boneh et al. [Itai Boneh et al., 2023] showed an O(n²) time algorithm for finding the hairpin completion distance between two strings of length at most n. In this paper we show that for any ε > 0 there is no O(n^{2-ε})-time algorithm for the hairpin completion distance problem unless the Strong Exponential Time Hypothesis (SETH) is false. Thus, under SETH, the time complexity of the hairpin completion distance problem is quadratic, up to sub-polynomial factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Boneh and Dvir Fried and Shay Golan and Matan Kraus 2024 Is Part Of LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2024.11 urn:nbn:de:0030-drops-201215 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode