Document Open Access Logo

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors

Author Amey Bhangale

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.15.pdf
  • Filesize: 0.54 MB
  • 11 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Hypergraph coloring
  • Inapproximability
  • Schrijver graph

Metrics

Abstract

We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,
1) It is NP-hard to color it with log^delta n colors for some delta>0.
2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.
In terms of NP-hardness, it improves the result of Guruswam, Håstad and Sudani [SIAM Journal on Computing, 2002], combined with Moshkovitz-Raz [Journal of the ACM, 2010], by an `exponential' factor. The second result improves the result of Saket [Conference on Computational Complexity (CCC), 2014] which shows quasi-NP-hardness of coloring a 2-colorable 4-uniform hypergraph with O(log^gamma n) colors for a sufficiently small constant 1 >> gamma>0.
Our result is the first to show the NP-hardness of coloring a c-colorable k-uniform hypergraph with poly-logarithmically many colors, for any constants c >= 2 and k >= 3.

Cite As Get BibTex

Amey Bhangale. NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.15

Author Details

Amey Bhangale
  • Weizmann Institute of Science, Rehovot, Israel

Funding

  • Bhangale, Amey: Research supported by Irit Dinur’s ERC-CoG grant 772839.

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. (Preliminary version in 33rd FOCS, 1992). URL: http://dx.doi.org/10.1145/278298.278306.
  2. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A new characterization of NP. JACM, 45(1):70-122, 1998. (Preliminary version in 33rd FOCS, 1992). Google Scholar
  3. J Bárány. A short proof of Kneser’s conjecture. Journal of Combinatorial Theory, Series A, 25(3):325-326, 1978. Google Scholar
  4. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In LIPIcs-Leibniz International Proceedings in Informatics, volume 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  5. I Dinur, O Regev, and C Smyth. The hardness of 3-uniform hypergraph coloring. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 33-40. IEEE, 2002. Google Scholar
  6. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268-292, 1996. Google Scholar
  7. Michael R Garey and David S Johnson. The complexity of near-optimal graph coloring. Journal of the ACM (JACM), 23(1):43-49, 1976. Google Scholar
  8. Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, and Girish Varma. Super-polylogarithmic Hypergraph Coloring Hardness via Low-degree Long Codes. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 614-623, New York, NY, USA, 2014. ACM. Google Scholar
  9. Venkatesan Guruswami, Johan Håstad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31(6):1663-1686, 2002. Google Scholar
  10. Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1):30-40, 2004. Google Scholar
  11. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. In Theory and Computing Systems, 1993., Proceedings of the 2nd Israel Symposium on the, pages 250-260. IEEE, 1993. Google Scholar
  12. Subhash Khot. Hardness results for approximate hypergraph coloring. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 351-359. ACM, 2002. Google Scholar
  13. Subhash Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 23-32. IEEE, 2002. Google Scholar
  14. Subhash Khot and Rishi Saket. Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp (log^Omega (1) n) Colors. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 206-215. IEEE, 2014. Google Scholar
  15. Subhash Khot and Rishi Saket. Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1607-1625. SIAM, 2014. Google Scholar
  16. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978. Google Scholar
  17. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. Journal of the ACM (JACM), 57(5):29, 2010. Google Scholar
  18. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  19. Rishi Saket. Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs. In IEEE 29th Conference on Computational Complexity (CCC), pages 78-89, 2014. Google Scholar
  20. A Schrijver. Vertex-critical subgraphs of Kneser-graphs. Nieuw Archief voor Wiskunde, 26:454-461, 1978. Google Scholar
  21. Girish Varma. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Chicago Journal OF Theoretical Computer Science, 3:1-8, 2015. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact