Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

Original · EN

A hypergraph is said to be χ-colorable if its vertices can be colored with χ colors so that no hyperedge is monochromatic. 2-colorability is a fundamental property (called Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a 2-colorable k-uniform hypergraph, it is NP-hard to find a 2-coloring miscoloring fewer than a fraction 2⁻ᵏ⁺¹ of hyperedges (which is achieved by a random 2-coloring), and the best algorithms to color the hypergraph properly require ≈ n¹⁻¹/ᵏ 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 2-coloring 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 2-colorability: (A) Low-discrepancy: If the hypergraph has discrepancy ℓ ≪ √k, we give an algorithm to color the it with ≈ nᵒ⁽ℓ²/ᵏ⁾ colors. However, for the maximization version, we prove NP-hardness of finding a 2-coloring miscoloring a smaller than 2⁻ᵒ⁽ᵏ⁾ (resp. k⁻ᵒ⁽ᵏ⁾) fraction of the hyperedges when ℓ = O(k) (resp. ℓ=2). Assuming the UGC, we improve the latter hardness factor to 2⁻ᵒ⁽ᵏ⁾ for almost discrepancy-1 hypergraphs. (B) Rainbow colorability: If the hypergraph has a (k-ℓ)-coloring such that each hyperedge is polychromatic with all these colors, we give a 2-coloring algorithm that miscolors at most k⁻Ω⁽ᵏ⁾ of the hyperedges when ℓ ≪ √k, and complement this with a matching UG hardness result showing that when ℓ =√k, it is hard to even beat the 2⁻ᵏ⁺¹ bound achieved by a random coloring.