Parameterized tractability of the maximum-duo preservation string mapping problem

Stefano Beretta, Mauro Castelli, Riccardo Dondi

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O(k6).

Original languageEnglish
Pages (from-to)16-25
Number of pages10
JournalTheoretical Computer Science
Publication statusPublished - 2016


  • Common string partition
  • Computational biology
  • Kernelization
  • Parameterized algorithms


Dive into the research topics of 'Parameterized tractability of the maximum-duo preservation string mapping problem'. Together they form a unique fingerprint.

Cite this