On the Complexity of BWT-runs Minimization via Alphabet Reordering
On the Complexity of BWT-runs Minimization via Alphabet Reordering
复制标题
DOI：
10.4230/lipics.esa.2020.15
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Jason Bentley;Daniel Gibney;Sharma V. Thankachan
中科院分区：
文献类型：
--
作者：
Jason Bentley;Daniel Gibney;Sharma V. Thankachan
我们给出了关于通过字母表重排来最小化BWT（Burrows - Wheeler变换）游程的计算复杂度的第一组结果。我们证明了这个问题的判定版本是NP完全的，并且除非指数时间假设不成立，否则它不能在$2^{o(\sigma)}n$的时间内被解决，其中$\sigma$是字母表的大小。此外，我们表明这个问题的优化变体产生了很强的不可近似性结果。在此过程中，我们将两个先前不同的主题联系起来：图的路径覆盖的大小和一个文本的BWT中的游程数量。这在图的问题和字符串压缩之间提供了一种令人惊讶的联系。因此我们能够证明（都假设P $\neq$ NP）：（i）如果我们将一个解的代价定义为恰好是超过$\sigma$的游程数量，那么不存在多项式时间近似方案（PTAS）；（ii）对于所有的$\delta > 0$，如果我们将超过$(1 + \delta)\sigma$的游程数量视为一个解的代价，那么对于足够小的$\epsilon > 0$，不存在多项式时间的$\epsilon n^{1/2}$ - 近似算法。在这种情况下，这个问题也是APX难的。据我们所知，这些是有史以来关于BWT的第一个不可近似性结果。此外，通过联系字典压缩领域的近期结果，我们证明如果我们纯粹将代价定义为游程数量，我们会得到一个$\log^2 n$ - 近似算法。最后，我们为一个更受限的问题提供了一个高效算法，该问题是在排序约束下找到一个符号子集（只出现一次）的最优排序，对于较小的$\sigma$值，该算法在最优时间内运行。我们还研究了在新发现的具有类似BWT性质的图类（称为惠勒图）上这个问题的一个版本。在这里，我们也展示了一个相关问题（我们称之为源排序）的NP难结果。
We present the first set of results on the computational complexity of minimizing BWT-runs via alphabet reordering. We prove that the decision version of this problem is NP-complete and cannot be solved in time $2^{o(\sigma)}n$ unless the Exponential Time Hypothesis fails, where $\sigma$ is the size of the alphabet. Moreover, we show that optimization variations of this problem yield strong inapproximability results. In doing so we relate two previously disparate topics: the size of a path cover of a graph and the number of runs in the BWT of a text. This provides a surprising connection between problems on graphs and string compression. As a result we are able to prove (all assuming P $\neq$ NP): (i) No PTAS exists if we define the cost of a solution as exactly the number of runs exceeding $\sigma$; (ii) For all $\delta > 0$, no polytime $\epsilon n^{1/2}$-approximation algorithm exists for $\epsilon > 0$ small enough if we consider the number of runs exceeding $(1+\delta)\sigma$ as the cost of a solution. In this case the problem is APX-hard as well. To the best of our knowledge these are the first ever inapproximability results pertaining to the BWT. In addition, by relating recent results in the field of dictionary compression, we demonstrate that if we define cost purely as the number of runs, we obtain a $\log^2 n$-approximation algorithm. Finally, we provide an efficient algorithm for the more restricted problem of finding an optimal ordering on a subset of symbols (occurring only once) under ordering constraints which runs in optimal time for small values of $\sigma$. We also look at a version of the problem on the newly discovered class of graphs with BWT like properties called Wheeler graphs. Here also we show NP-hardness results on a related problem which we call Source Ordering.