Improved Inapproximability of Rainbow Coloring
Improved Inapproximability of Rainbow Coloring
复制标题
改进了彩虹着色的不近似性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Aditya Potukuchi
中科院分区：
文献类型：
--
作者：
Per Austrin;Amey Bhangale;Aditya Potukuchi
一个k-一致超图的彩虹q-染色是顶点集的q-染色，使得每一个超边都包含所有q-色。
我们证明了给定一个彩虹$（k - 2\lfloor \sqrt{k}\rfloor）$-可着色的$k$-一致超图，找到正常的$2$-着色是NP-困难的.在此之前，这只为彩虹$\lfloor k/2 \rfloor$-可着色超图所知（Guruswami and Lee，SODA 2015）。
我们还研究了一个推广，我们称之为彩虹$（q，p）$-着色，定义为一个着色使用$q$颜色，使每个超边至少包含$p$颜色。我们证明了给定一个彩虹$（k - \lfloor \sqrt{kc} \rfloor，k-\lfloor 3\sqrt {kc} \rfloor）$-可着色的$k$一致超图，对于任意常数$c < k/10$，找到正常$c$-着色是NP-困难的.
我们的第二个结果的证明依赖于两个组合定理。Sarkaria（J.~梳吧~理论。~ 1990年）使用拓扑方法和其他定理，我们证明了使用广义Borsuk-Ulam定理。
A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors.
We prove that given a rainbow $(k - 2\lfloor \sqrt{k}\rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $\lfloor k/2 \rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015).
We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - \lfloor \sqrt{kc} \rfloor, k- \lfloor3\sqrt{kc} \rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any constant $c < k/10$.
The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J.~Comb.~Theory.~1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
影响因子：
1.3
作者：
Brakensiek, Joshua;Guruswami, Venkatesan
通讯作者：
Guruswami, Venkatesan