2026-07-23T08:19:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9939 2024-03-06T10:45:09Z ddc:004 open_access

Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS Bringmann, Karl Chaudhury, Bhaskar Ray algorithms SETH communication complexity run-length encoding We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size |Sigma|. For the problem of deciding whether the LCS of strings x,y has length at least L, we obtain a sketch size and streaming space usage of O(L^{|Sigma| - 1} log L). We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an O(min{nm, n + m^{|Sigma|}})-time algorithm for this problem, on strings x,y of length n,m, with n >= m. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Bhaskar Ray Chaudhury 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.40 urn:nbn:de:0030-drops-99390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.40 eng https://creativecommons.org/licenses/by/3.0/legalcode