Hardness results for coloring 3-colorable 3-uniform hypergraphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 δn for an arbitrarily small constant δ > 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 8/9 + ε fraction of the edges non-monochromatic where ε > 0 is an arbitrarily small constant. This result is tight since assigning a random color independently to every vertex makes 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 δn.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
EditorsD.C. Martin
Pages23-32
Number of pages10
StatePublished - 2002
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

Other

OtherThe 34rd Annual IEEE Symposium on Foundations of Computer Science
CountryCanada
CityVancouver, BC
Period11/16/0211/19/02

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Hardness results for coloring 3-colorable 3-uniform hypergraphs'. Together they form a unique fingerprint.

  • Cite this

    Khot, S. (2002). Hardness results for coloring 3-colorable 3-uniform hypergraphs. In D. C. Martin (Ed.), Annual Symposium on Foundations of Computer Science - Proceedings (pp. 23-32)