An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions

Laurent Bulteau*, Mark Jones, Rolf Niedermeier, Till Tantau

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Downloads (Pure)

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.

Original languageEnglish
Title of host publication33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
EditorsHideo Bannai, Jan Holub
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages11
ISBN (Electronic)9783959772341
DOIs
Publication statusPublished - 2022
Event33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 - Prague, Czech Republic
Duration: 27 Jun 202229 Jun 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume223
ISSN (Print)1868-8969

Conference

Conference33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
Country/TerritoryCzech Republic
CityPrague
Period27/06/2229/06/22

Keywords

  • center string
  • enumerative algorithms
  • multiple sequence alignment
  • NP-hard string problems
  • parameterized complexity
  • search tree algorithms

Fingerprint

Dive into the research topics of 'An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions'. Together they form a unique fingerprint.

Cite this