Bhattiprolu, Vijay V. S. P. ;
Guruswami, Venkatesan ;
Lee, Euiwoong
Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises
Abstract
A hypergraph is said to be Xcolorable if its vertices can be colored with X colors so that no hyperedge is monochromatic. 2colorability is a fundamental property (called Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a 2colorable kuniform hypergraph, it is NPhard to find a 2coloring miscoloring fewer than a fraction 2^(k+1) of hyperedges (which is trivially achieved by a random 2coloring), and the best algorithms to color the hypergraph properly require about n^(11/k) colors, approaching the trivial bound of n as k increases.
In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a 2coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have the following stronger properties than 2colorability:
(A) Lowdiscrepancy: If the hypergraph has a 2coloring of discrepancy l << sqrt(k), we give an algorithm to color the hypergraph with about n^(O(l^2/k)) colors. However, for the maximization version, we prove NPhardness of finding a 2coloring miscoloring a smaller than 2^(O(k)) (resp. k^(O(k))) fraction of the hyperedges when l = O(log k) (resp. l=2). Assuming the Unique Games conjecture, we improve the latter hardness factor to 2^(O(k)) for almost discrepancy1 hypergraphs.
(B) Rainbow colorability: If the hypergraph has a (kl)coloring such that each hyperedge is polychromatic with all these colors (this is stronger than a (l+1)discrepancy 2coloring), we give a 2coloring algorithm that miscolors at most k^(Omega(k)) of the hyperedges when l << sqrt(k), and complement this with a matching Unique Games hardness result showing that when l = sqrt(k), it is hard to even beat the 2^(k+1) bound achieved by a random coloring.
(C) Strong Colorability: We obtain similar (stronger) Min and Max2Coloring algorithmic results in the case of (k+l)strong colorability.
BibTeX  Entry
@InProceedings{bhattiprolu_et_al:LIPIcs:2015:5301,
author = {Vijay V. S. P. Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee},
title = {{Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {152174},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5301},
URN = {urn:nbn:de:0030drops53011},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.152},
annote = {Keywords: Hypergraph Coloring, Discrepancy, Rainbow Coloring, Stong Coloring, Algorithms, Semidefinite Programming, Hardness of Approximation}
}
13.08.2015
Keywords: 

Hypergraph Coloring, Discrepancy, Rainbow Coloring, Stong Coloring, Algorithms, Semidefinite Programming, Hardness of Approximation 
Seminar: 

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

Issue date: 

2015 
Date of publication: 

13.08.2015 