Tata Institute of Fundamental Research
Improved NP-hardness of Hypergraph Rainbow Coloring
STCS Seminar
Speaker:
Amey Bhangale (Dept. of Applied Math and Computer Science
The Weizmann Institute of Science
Ziskind building, Room 246
Rehovot, 76100 ISRAEL)
Organiser:
Prahladh Harsha
Date:
Tuesday, 3 Jul 2018, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Amey Bhangale (Dept. of Applied Math and Computer Science The Weizmann Institute of Science Ziskind building, Room 246 Rehovot, 76100 ISRAEL) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 3 Jul 2018, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).