A $k$-attractor is a combinatorial object unifying dictionary-based compression. It allows to compare the repetitiveness measures of different dictionary compressors such as Lempel-Ziv 77, the Burrows-Wheeler transform, straight line programs and macro schemes. For a string $ T \in \Sigma^n$, the $k$-attractor is defined as a set of positions $\Gamma \subseteq [1,n]$, such that every distinct substring of length at most $k$ is covered by at least one of the selected positions. Thus, if a substring occurs multiple times in $T$, one position suffices to cover it. A 1-attractor is easily computed in linear time, while Kempa and Prezza [STOC 2018] have shown that for $k \geq 3$, it is NP-complete to compute the smallest $k$-attractor by a reduction from $k$-set cover. The main result of this paper answers the open question for the complexity of the 2-attractor problem, showing that the problem remains NP-complete. Kempa and Prezza's proof for $k \geq 3$ also reduces the 2-attractor problem to the 2-set cover problem, which is equivalent to edge cover, but that does not fully capture the complexity of the 2-attractor problem. For this reason, we extend edge cover by a color function on the edges, yielding the colorful edge cover problem. Any edge cover must then satisfy the additional constraint that each color is represented. This extension raises the complexity such that colorful edge cover becomes NP-complete while also more precisely modeling the 2-attractor problem. We obtain a reduction showing $k$-attractor to be NP-complete for any $k \geq 2$.


翻译:$k$-吸引子是一种组合对象,用于统一基于字典的压缩。它允许比较不同字典压缩器(如Lempel-Ziv 77、Burrows-Wheeler变换、直线程序和宏方案)的重复度量。对于字符串$T\in\Sigma^n$,$k$-吸引子定义为位置集$\Gamma\subseteq[1,n]$,使得每个长度最多为$k$的不同子字符串都被至少一个选定的位置覆盖。因此,如果一个子字符串在$T$中出现多次,则一个位置就足以覆盖它。1-吸引子可以在线性时间内轻松计算,而Kempa和Prezza [STOC 2018]已经证明对于$k\geq 3$,通过从$k$-集覆盖的约简,计算最小的$k$-吸引子是NP完全的。本文的主要结果回答了2-吸引子问题的开放问题,表明该问题仍然是NP完全的。Kempa和Prezza对于$k\geq 3$的证明还将2-吸引子问题简化为2-集覆盖问题,这相当于边覆盖,但这并不能完全捕捉2-吸引子问题的复杂性。因此,我们通过边缘上的颜色函数来扩展边缘覆盖,从而产生了彩色边缘覆盖问题。然后,任何边缘覆盖必须满足附加的约束条件,即每种颜色都应表示。此扩展提高了所需的复杂度,以使彩色边缘覆盖变为NP完全,同时更准确地建模2-吸引子问题。我们获得了一种约简方法,可以将$k\geq 2$的$k$-吸引子证明为NP完全。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
论文共读 | Attention is All You Need
黑龙江大学自然语言处理实验室
14+阅读 · 2017年9月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月28日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
论文共读 | Attention is All You Need
黑龙江大学自然语言处理实验室
14+阅读 · 2017年9月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员