Hardness results for approximate hypergraph coloring

ABSTRACT

(MATH) Guruswami et al [6] show the hardness of coloring 2-colorable 4-uniform hypergraphs on n vertices with ω(^{log log n} \over _{log log log n}}) colors assuming NP $\not\subseteq$ DTIME(n^{O log log n)}). We obtain a stronger hardness result for approximate coloring of p-colorable 4-uniform hypergraphs for any fixed integer p &rhoe; 7. We prove that there exists an absolute constant c ρ 0 such that for every fixed integer p &rhoe; 7, it is hard to color a p-colorable 4-uniform hypergraph with (log n)^cp colors assuming NP $\not \subseteq$ DTIME(2^{(log n)O(1)}).This work builds on the idea of "covering complexity" of probabilistically checkable proof systems (PCPs) developed in [6] and we introduce some new techniques as well. Firstly, we define a new code which we call the Split Code. This is a variation of the Long Code, but much shorter in length and it reduces the proof size significantly. Split Codes enable us to exploit the special structure of the "outer PCP verifier" constructed via Raz's Parallel Repetition Theorem [18]. Secondly, we make a novel use of the Split Codes over the domain GF(p) for a prime p. Working over non-boolean domain in fact makes our proof technically simpler than the proof of Guruswami at al [6].

REFERENCES

• 1: Noga Alon , Pierre Kelsen , Sanjeev Mahajan , Hariharan Ramesh, Coloring 2-colorable hypergraphs with a sublinear number of colors, Nordic Journal of Computing, v.3 n.4, p.425-439, Winter 1996
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 4: M. Bellare, O. Goldreich, and M. Sudan. Free bits, pcps and non-approximability. Electronic Colloquium on Computational Complexity, Technical Report TR95-024, 1995.
• 5: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• 6: V. Guruswami , J. Hastad , M. Sudan, Hardness of approximate hypergraph coloring, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.149, November 12-14, 2000
• 7: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 8: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 9: Johan Håstad , S. Venkatesh, On the advantage over a random assignment, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509916]
• 10: Jonas Holmerin, Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - &egr;, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509986]
• 11: D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In Proc. of the 35th IEEE Symposium on Foundations of Computer Science, 1994.
• 12: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 13: Michael Krivelevich , Benny Sudakov, Approximate Coloring of Uniform Hypergraphs (Extended Abstract), Proceedings of the 6th Annual European Symposium on Algorithms, p.477-489, August 24-26, 1998
• 14: L. Lovász. Coverings and colorings of hypergraphs. In Proc. of 4th Southeastern Conf. on Combinatorics, Graph Theory and Computing, pages 3--12. Utilitas (MATH)ematica Publishing, Winnipeg, 1973.
• 15: C. McDiarmid. A random recoloring method for graphs and hypergraphs. Combinatorics, Probability and Computing, 2:363--365, 1993.
• 16: Colin McDiarmid, Hypergraph colouring and the Lovász local lemma, Discrete Mathematics, 167-168, p.481-486, April 15, 1997 [doi>10.1016/S0012-365X(96)00249-X]
• 17: Jaikumar Radhakrishnan , Aravind Srinivasan, Improved Bounds and Algorithms for Hypergraph Two-Coloring, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.684, November 08-11, 1998
• 18: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.2 Approximation
          Subjects: Linear approximation

General Terms:
Algorithms, Experimentation, Performance, Theory