STRONG INAPPROXIMABILITY RESULTS ON BALANCED RAINBOW-COLORABLE HYPERGRAPHS

摘要

Consider a K-uniform hypergraph H = (V,E). A coloring c: V → {1,2,...,k} with k colors is rainbow if every hyperedge e contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A simple polynomial-time algorithm finds a 2-coloring if H admits a perfectly balanced rainbow k-coloring. For a hypergraph that admits an almost balanced rainbow coloring, we prove that it is NP-hard to find an independent set of size ε, for any ε > 0. Consequently, we cannot weakly color (avoiding monochromatic hyperedges) it with O(1) colors. With k =2, it implies strong hardness for discrepancy minimization of systems of bounded set-size.