Guruswami, Venkatesan ;
Saket, Rishi
Hardness of Rainbow Coloring Hypergraphs
Abstract
A hypergraph is krainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any Q,k >= 2 and \ell <= k/2, given a Qkuniform hypergraph which admits a krainbow coloring satisfying:
 in each hyperedge e, for some \ell_e <= \ell all but 2\ell_e colors occur exactly Q times and the rest (Q +/ 1) times,
it is NPhard to compute an independent set of (1  (\ell+1)/k + \eps)fraction of vertices, for any constant \eps > 0. In particular, this implies the hardness of even (k/\ell)rainbow coloring such hypergraphs.
The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the krainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of \omega(1)coloring 2colorable 4uniform hypergraphs due to Saket, and krainbow colorable 2kuniform hypergraphs due to Guruswami and Lee.
BibTeX  Entry
@InProceedings{guruswami_et_al:LIPIcs:2018:8390,
author = {Venkatesan Guruswami and Rishi Saket},
title = {{Hardness of Rainbow Coloring Hypergraphs}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {33:3333:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770552},
ISSN = {18688969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8390},
URN = {urn:nbn:de:0030drops83905},
doi = {10.4230/LIPIcs.FSTTCS.2017.33},
annote = {Keywords: Fourier analysis of Boolean functions, hypergraph coloring, Inapproximability, Label Cover, PCP}
}
12.02.2018
Keywords: 

Fourier analysis of Boolean functions, hypergraph coloring, Inapproximability, Label Cover, PCP 
Seminar: 

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Issue date: 

2018 
Date of publication: 

12.02.2018 