Improved NP-hardness of Hypergraph Rainbow Coloring


Amey Bhangale


Dept. of Applied Math and Computer Science
The Weizmann Institute of Science
Ziskind building, Room 246
Rehovot, 76100 ISRAEL


Tuesday, 3 July 2018, 14:00 to 15:00


  • A-201 (STCS Seminar Room)


A k-uniform hypergraph is defined to be q-rainbow colorable (q\leq k) if there exists a coloring of the vertex set with q colors such that every hyperedge contains all the q colors. Given a k-uniform hypergraph which is q rainbow colorable for some q, can we at least find a 2 coloring in polynomial time? This problem comes under the so called *promise* constraint satisfaction problems.

We show that given a k-uniform hypergraph which is (k - 2\sqrt{k})-rainbow colorable, it is NP-hard to find a 2-coloring of it. This improves the result of Guruswami-Lee. We also show NP-hardness of finding a c-coloring of an approximate rainbow colorable (a slightly weaker notion than the rainbow coloring) hypergraph for large c (joint work with Per Austrin and Aditya Potukuchi).