تقرير
Weighted Shortest Common Supersequence Problem Revisited
العنوان: | Weighted Shortest Common Supersequence Problem Revisited |
---|---|
المؤلفون: | Charalampopoulos, Panagiotis, Kociumaka, Tomasz, Pissis, Solon P., Radoszewski, Jakub, Rytter, Wojciech, Straszyński, Juliusz, Waleń, Tomasz, Zuba, Wiktor |
سنة النشر: | 2019 |
المجموعة: | Computer Science |
مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
الوصف: | A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on weighted strings. In the WSCS problem, we are given two weighted strings $W_1$ and $W_2$ and a threshold $\mathit{Freq}$ on probability, and we are asked to compute the shortest (standard) string $S$ such that both $W_1$ and $W_2$ match subsequences of $S$ (not necessarily the same) with probability at least $\mathit{Freq}$. Amir et al. showed that this problem is NP-complete if the probabilities, including the threshold $\mathit{Freq}$, are represented by their logarithms (encoded in binary). We present an algorithm that solves the WSCS problem for two weighted strings of length $n$ over a constant-sized alphabet in $\mathcal{O}(n^2\sqrt{z} \log{z})$ time. Notably, our upper bound matches known conditional lower bounds stating that the WSCS problem cannot be solved in $\mathcal{O}(n^{2-\varepsilon})$ time or in $\mathcal{O}^*(z^{0.5-\varepsilon})$ time unless there is a breakthrough improving upon long-standing upper bounds for fundamental NP-hard problems (CNF-SAT and Subset Sum, respectively). We also discover a fundamental difference between the WSCS problem and the Weighted Longest Common Subsequence (WLCS) problem, introduced by Amir et al. [JDA 2010]. We show that the WLCS problem cannot be solved in $\mathcal{O}(n^{f(z)})$ time, for any function $f(z)$, unless $\mathrm{P}=\mathrm{NP}$. Comment: Accepted to SPIRE'19 |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/1909.11433 |
رقم الأكسشن: | edsarx.1909.11433 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |