Improved NP-hardness of Hypergraph Rainbow Coloring

by Amey Bhangale (The Weizmann Institute of Science, Israel)

Tuesday 3 Jul 2018, 14:00 → 15:00 Asia/Kolkata

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).