On the Complexity of Recognizing Wheeler Graphs
On the Complexity of Recognizing Wheeler Graphs
复制标题
论识别惠勒图的复杂性
DOI：
10.1007/s00453-021-00917-5
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Thankachan, Sharma V.
中科院分区：
文献类型：
--
作者：
Gibney, Daniel;Thankachan, Sharma V.
近年来，基于Burrows-Wheeler变换的几种压缩指数被引入。其中一些用于索引比单个字符串复杂得多的结构，如最初使用FM索引所做的那样（Ferragina和曼齐尼in J. ACM 52（4）：552-581，https：//doi.org/10.1145/1082036.1082039，2005）。因此，人们越来越努力地更好地理解在什么条件下这种索引方案是可能的。这导致了惠勒图的引入（Gagie et al. in Theor Comput Sci 698：67-78，https：//doi.org/10.1016/j.tcs.2017.06.016，2017）。Gagie等人证明了de Bruijn图、广义压缩后缀数组和其他几个BWT相关结构可以表示为惠勒图，并且惠勒图可以以空间有效的方式索引。因此，能够识别给定图是否是惠勒图，或者能够通过惠勒图来近似给定图，可以在索引中具有许多应用。在这里，我们解决了一个开放的问题，是否存在一个有效的算法来识别，如果一个给定的图是一个惠勒图。我们表明：识别一个给定的graphis一个惠勒图的问题是NP-完全的任何边标签字母的大小，即使当G是一个DAG。这甚至适用于一个受限制的子集的图称为NFA。这与最近的结果相反，这些结果表明该问题可以在多项式时间内解决。我们还证明了在无自环的图上，识别问题可以在线性时间内求解，并且存在一个时间精确算法。该算法依赖于图同构计算在严格的次指数时间，我们定义了一个优化的变种的问题称为惠勒图违规，简称WGV，其目的是确定最小的一组边缘，必须从一个图中删除，以获得一个惠勒图。我们证明了WGV是APX-难的，即使当G是DAG时，这意味着存在一个常数，对于该常数没有C-近似算法（除非P = NP）。此外，在唯一博弈猜想的条件下，对于所有人来说，找到一个C-近似是NP-困难的，这意味着WGV不在APX中;我们定义了惠勒子图问题，简称WS，其目的是找到最大的子图，这是一个惠勒图（WGV的对偶）。与WGV相比，我们给出了WS问题的一个近似算法，这意味着它在APX中。上述研究结果表明，在这个主题下的大多数问题是计算困难的。然而，我们确定了一类图形的识别问题是多项式时间可解的，提出了问题的属性决定这个问题的难度。
In recent years, severalcompressed indexesbased on variants of the Burrows–Wheeler transform have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index (Ferragina and Manzini in J. ACM 52(4):552–581, https://doi.org/10.1145/1082036.1082039, 2005). As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs (Gagie et al. in Theor Comput Sci 698:67–78, https://doi.org/10.1016/j.tcs.2017.06.016, 2017). Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs, and that Wheeler graphs can be indexed in a space-efficient way. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We show:The problem of recognizing whether a given graphis a Wheeler graph is NP-complete for any edge label alphabet of size, even whenGis a DAG. This holds even on a restricted subset of graphs calledd-NFAs for. This is in contrast to recent results demonstrating the problem can be solved in polynomial time ford-NFAs where. We also show that the recognition problem can be solved in linear time foron graphs without self-loops;There exists antime exact algorithm whereand. This algorithm relies on graph isomorphism being computable in strictly sub-exponential time;We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to identify the smallest set of edges that have to be removed from a graph to obtain a Wheeler graph. We show WGV is APX-hard, even whenGis a DAG, implying there exists a constantfor which there is noC-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all, it is NP-hard to find aC-approximation, implying WGV is not in APX;We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of WGV). In contrast to WGV, we give an-approximation algorithm for the WS problem, implying it is in APX for.The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial-time solvable, raising the question of which properties determine this problem’s difficulty.
登录
查看更多内容
pBWT：实现参数化模式匹配和相关问题的简洁数据结构
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Arnab Ganguly;Rahul Shah;Sharma V. Thankachan
通讯作者：
Sharma V. Thankachan
通过 PQ 树进行全基因组基因邻近分析1
DOI：
--
发表时间：
2005
期刊：
J. Comput. Biol.
影响因子：
--
作者：
G. M. Landau;L. Parida;Oren Weimann
通讯作者：
Oren Weimann
简洁的字典匹配，不拖慢速度
DOI：
--
发表时间：
2010
期刊：
Annual Symposium on Combinatorial Pattern Matching
影响因子：
--
作者：
Djamal Belazzougui
通讯作者：
Djamal Belazzougui
有向无环图的堆栈和队列布局：第一部分
DOI：
--
发表时间：
1999
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Lenwood S. Heath;Sriram V. Pemmaraju;Ann N. Trenk
通讯作者：
Ann N. Trenk
DOI：
10.1137/1.9781611975994.55
发表时间：
2019-02
期刊：
--
影响因子：
--
作者：
Jarno N. Alanko;G. D’Agostino;A. Policriti;N. Prezza
通讯作者：
Jarno N. Alanko;G. D’Agostino;A. Policriti;N. Prezza