Warianty problemu znajdowania najdłuższego wspólnego podciągu oraz powiązane problemy

Problem znajdowania najdłuższego wspólnego podciągu jest niewątpliwie bardzo dobrze znanym zagadnieniem algorytmicznym, a jego rozwiązanie dla przypadku dwóch słów wejściowych przedstawia się zazwyczaj jako jeden ze sztandarowych przykładów zastosowania techniki programowania dynamicznego. W tej pracy przedstawimy wybrane rezultaty z ostatnich lat dotyczące różnych wariantów problemu (takich jak najdłuższy wspólny podciąg niezawierający powtórzeń), a także niektórych problemów pokrewnych, na przykład odległości edycyjnej lub Dynamic Time Warping Distance. Poświęcimy część uwagi wieloparametrycznemu podejściu do analizy złożoności – w szczególności przedstawimy kilka ograniczeń dolnych na złożoność czasową problemu (warunkowanych hipotezą SETH) zależnych od dodatkowych parametrów napisów wejściowych.

Longest Common Subsequence (abbreviated LCS) is one of the most well-known algorithmic problems, and its solution (for the case of two input sequences) is usually among the first examples of dynamic programming approaches shown in most introductory algorithmic courses. In this thesis, we aim to present recent results regarding various variants of the problem such as Repetition-Free Longest Common Subsequence, as well as some related problems, including Edit Distance or Dynamic Time Warping Distance. We will also pay extra attention to a multivariate approach to the problem – in particular we will state some conditional lower bounds on time complexity in terms of additional properties of the input strings.