Quasi NP hard to color 2 colorable 3 uniform hypergraphs with few colors
Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{Ω(1)} n$ Colors
Computational Complexity
Summary
The paper deals with a type of mathematical puzzle called hypergraph coloring, where you want to color points so that certain groups don’t all share the same color. The authors show that even if the hypergraph can be colored with just two colors, it is extremely hard to find a coloring using only a small number of colors—specifically, as hard as problems believed to be very difficult to solve quickly. This result improves on past work by showing the problem remains hard when allowing many more colors, growing roughly like a power of the logarithm of the size of the problem.
What this means in practice
- •For complexity theorists: Use this hardness result as a benchmark to understand limitations of efficient algorithms for coloring certain hypergraphs.
- •For algorithm designers: Know that efficient algorithms to color 2-colorable 3-uniform hypergraphs with few colors likely cannot exist due to this hardness result.
A theory result. No direct application yet.
Authors
Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles
Abstract
We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.