Guruswami, Venkatesan ;
Sandeep, Sai
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Abstract
A kuniform hypergraph is said to be rrainbow colorable if there is an rcoloring of its vertices such that every hyperedge intersects all r color classes. Given as input such a hypergraph, finding a rrainbow coloring of it is NPhard for all k >= 3 and r >= 2. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When r=k (the maximum possible value), i.e., the hypergraph is kpartite, one can efficiently 2rainbow color the hypergraph, i.e., 2color its vertices so that there are no monochromatic edges. In this work we consider the next smaller value of r=k1, and prove that in this case it is NPhard to rainbow color the hypergraph with q := ceil[(k2)/2] colors. In particular, for k <=6, it is NPhard to 2color (k1)rainbow colorable kuniform hypergraphs.
Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set [r]^n. We prove that any such polymorphism f: [r]^n > [q] must be Cfixing, i.e., there is a small subset S of C coordinates and a setting a in [q]^S such that fixing x_{S} = a determines the value of f(x). The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the Cfixing characterization, our NPhardness is obtained via a reduction from smooth Label Cover.
BibTeX  Entry
@InProceedings{guruswami_et_al:LIPIcs:2019:11230,
author = {Venkatesan Guruswami and Sai Sandeep},
title = {{Rainbow Coloring Hardness via Low Sensitivity Polymorphisms}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {15:115:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11230},
URN = {urn:nbn:de:0030drops112303},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.15},
annote = {Keywords: inapproximability, hardness of approximation, constraint satisfaction, hypergraph coloring, polymorphisms}
}
17.09.2019
Keywords: 

inapproximability, hardness of approximation, constraint satisfaction, hypergraph coloring, polymorphisms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 