Print Email Facebook Twitter An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions Title An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions Author Bulteau, Laurent (Université Gustave Eiffel, Marne-la-vallé) Jones, M.E.L. (TU Delft Discrete Mathematics and Optimization) Niedermeier, Rolf (Technical University of Berlin) Tantau, Till (University of Lübeck) Contributor Bannai, Hideo (editor) Holub, Jan (editor) Date 2022 Abstract In the NP-hard Longest Common Subsequence problem (LCS), given a set of strings, the task is to find a string that can be obtained from every input string using as few deletions as possible. LCS is one of the most fundamental string problems with numerous applications in various areas, having gained a lot of attention in the algorithms and complexity research community. Significantly improving on an algorithm by Irving and Fraser [CPM'92], featured as a research challenge in a 2014 survey paper, we show that LCS is fixed-parameter tractable (FPT) when parameterized by the maximum number of deletions per input string. Given the relatively moderate running time of our algorithm (linear time when the parameter is a constant) and small parameter values to be expected in several applications, we believe that our purely theoretical analysis could finally pave the way to a new, exact and practically useful algorithm for this notoriously hard string problem. Subject center stringenumerative algorithmsmultiple sequence alignmentNP-hard string problemsparameterized complexitysearch tree algorithms To reference this document use: http://resolver.tudelft.nl/uuid:d08de189-661c-44b6-a3da-54b2585eb00f DOI https://doi.org/10.4230/LIPIcs.CPM.2022.6 Publisher Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing ISBN 9783959772341 Source 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 Event 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, 2022-06-27 → 2022-06-29, Prague, Czech Republic Series Leibniz International Proceedings in Informatics, LIPIcs, 1868-8969, 223 Part of collection Institutional Repository Document type conference paper Rights © 2022 Laurent Bulteau, M.E.L. Jones, Rolf Niedermeier, Till Tantau Files PDF LIPIcs_CPM_2022_6.pdf 863.06 KB Close viewer /islandora/object/uuid:d08de189-661c-44b6-a3da-54b2585eb00f/datastream/OBJ/view