2026-07-22T08:25:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7343 2024-03-06T10:40:06Z ddc:004 open_access

Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping Komusiewicz, Christian de Oliveira Oliveira, Mateus Zehavi, Meirav comparative genomics parameterized complexity kernelization In the Maximum-Duo Preservation String Mapping (Max-Duo PSM) problem, the input consists of two related strings A and B of length n and a nonnegative integer k. The objective is to determine whether there exists a mapping m from the set of positions of A to the set of positions of B that maps only to positions with the same character and preserves at least k duos, which are pairs of adjacent positions. We develop a randomized algorithm that solves Max-Duo PSM in time 4^k * n^{O(1)}, and a deterministic algorithm that solves this problem in time 6.855^k * n^{O(1)}. The previous best known (deterministic) algorithm for this problem has running time (8e)^{2k+o(k)} * n^{O(1)} [Beretta et al., Theor. Comput. Sci. 2016]. We also show that Max-Duo PSM admits a problem kernel of size O(k^3), improving upon the previous best known problem kernel of size O(k^6). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Mateus de Oliveira Oliveira and Meirav Zehavi 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.11 urn:nbn:de:0030-drops-73436 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.11 eng https://creativecommons.org/licenses/by/3.0/legalcode