|
Published Articles >> Table of Contents >> Abstract
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
p. 23
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs
Subhash Khot, Princeton University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181879
Send link to a friend
| Abstract |
|
In this paper, we consider the problem of coloring a 3-colorable 3-uniform hypergraph. In the minimization version of this problem, given a 3-colorable 3-uniform hypergraph, one seeks an algorithm to color the hypergraph with as few colors as possible. We show that it is NP-hard to color a 3-colorable 3-uniform hypergraph with constantly many colors. In fact, we show a stronger result that it is NP-hard to distinguish whether a 3-uniform hypergraph with n vertices is 3-colorable or it contains no independent set of size \delta n for an arbitrarily small constant \delta >0. In the maximization version of the problem, given a 3-uniform hypergraph, the goal is to color the vertices with 3 colors so as to maximize the number of non-monochromatic edges. We show that it is NP-hard to distinguish whether a 3-uniform hypergraph is 3-colorable or any coloring of the vertices with 3 colors has at most \frac{8}{9} + \varepsilon fraction of the edges non-monochromatic where \varepsilon > 0 is an arbitrarily small constant. This result is tight since assigning a random color independently to every vertex makes \frac{8}{9} fraction of the edges non-monochromatic. These results are obtained via a new construction of a probabilistically checkable proof system (PCP) for NP. We develop a new construction of the PCP Outer Verifier. An important feature of this construction is smoothening of the projection maps. Dinur, Regev and Smyth [6] independently showed that it is NP-hard to color a 2-colorable 3-uniform hypergraph with constantly many colors. In the "good case", the hypergraph they construct is 2-colorable and hence their result is stronger. In the "bad case" however, the hypergraph we construct has a stronger property, namely, it does not even contain an independent set of size \delta n.
|
 Additional Information
|
Citation:
Subhash Khot,
"Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs,"
focs,
p. 23,
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02),
2002
|
|
