NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
复制标题
具有多对数颜色的着色 2 色超图的 NP 硬度
DOI：
10.4230/lipics.icalp.2018.15
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Amey Bhangale
中科院分区：
文献类型：
--
作者：
Amey Bhangale
我们给出了以下陈述的非常简短的证明：给定n个顶点上的2-可着色4-一致超图，
1)对于某些delta>0，用log^delta n种颜色对其着色是NP困难的。
2)这是一个伪NP-困难的问题，需要O（{log^{1-o（1）} n}）的颜色。
在NP-硬度方面，它改进了Guruswam，Hastad和Sudani [SIAM Journal on Computing，2002]与Moshkovitz-Raz [Journal of the ACM，2010]结合的结果，通过“指数”因子。第二个结果改进了Saket [Conference on Computational Complexity（CCC），2014]的结果，该结果显示了对于足够小的常数1 >> gamma>0，用O（log^gamma n）颜色着色2-可着色4-均匀超图的准NP-硬度。
本文的结果首次证明了对任意常数c >= 2和k >= 3，用多色数着色c-可着色k-一致超图的NP-困难性.
We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,
1) It is NP-hard to color it with log^delta n colors for some delta>0.
2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.
In terms of NP-hardness, it improves the result of Guruswam, Hastad and Sudani [SIAM Journal on Computing, 2002], combined with Moshkovitz-Raz [Journal of the ACM, 2010], by an `exponential' factor. The second result improves the result of Saket [Conference on Computational Complexity (CCC), 2014] which shows quasi-NP-hardness of coloring a 2-colorable 4-uniform hypergraph with O(log^gamma n) colors for a sufficiently small constant 1 >> gamma>0.
Our result is the first to show the NP-hardness of coloring a c-colorable k-uniform hypergraph with poly-logarithmically many colors, for any constants c >= 2 and k >= 3.