TY - GEN
T1 - An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions
AU - Bulteau, Laurent
AU - Jones, Mark
AU - Niedermeier, Rolf
AU - Tantau, Till
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - center string
KW - enumerative algorithms
KW - multiple sequence alignment
KW - NP-hard string problems
KW - parameterized complexity
KW - search tree algorithms
UR - http://www.scopus.com/inward/record.url?scp=85134309993&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2022.6
DO - 10.4230/LIPIcs.CPM.2022.6
M3 - Conference contribution
AN - SCOPUS:85134309993
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
A2 - Bannai, Hideo
A2 - Holub, Jan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
Y2 - 27 June 2022 through 29 June 2022
ER -