Loading...
Please wait, while we are loading the content...
Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping
| Content Provider | Paperity |
|---|---|
| Author | Oliveira, Mateus De Oliveira Komusiewicz, Christian Zehavi, Meirav |
| Abstract | 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). |
| Starting Page | 11:1 |
| Ending Page | 11:17 |
| File Format | HTM / HTML |
| DOI | 10.4230/LIPIcs.CPM.2017.11 |
| Journal | Leibniz International Proceedings in Informatics |
| Volume Number | 78 |
| Language | English |
| Publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| Publisher Date | 2017-06-28 |
| Access Restriction | Open |
| Subject Keyword | Comparative genomics Parameterized complexity Kernelization |
| Content Type | Text |
| Resource Type | Article |
