Document Open Access Logo

Hardness of Rainbow Coloring Hypergraphs

Authors Venkatesan Guruswami, Rishi Saket

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.33.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Venkatesan Guruswami
Rishi Saket

Cite As Get BibTex

Venkatesan Guruswami and Rishi Saket. Hardness of Rainbow Coloring Hypergraphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.33

Abstract

A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are  guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any Q,k >= 2 and \ell <= k/2, given a Qk-uniform hypergraph which admits a k-rainbow coloring satisfying:

- in each hyperedge e, for some \ell_e <= \ell all but 2\ell_e colors occur exactly Q times and the rest (Q +/- 1) times, 

it is NP-hard to compute an independent set of (1 - (\ell+1)/k + \eps)-fraction of vertices, for any constant \eps > 0. In particular, this implies the hardness of even (k/\ell)-rainbow  coloring such hypergraphs. 

The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the k-rainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of \omega(1)-coloring 2-colorable 4-uniform hypergraphs due to Saket, and k-rainbow colorable 2k-uniform hypergraphs due to Guruswami and Lee.

Subject Classification

Keywords
  • Fourier analysis of Boolean functions
  • hypergraph coloring
  • Inapproximability
  • Label Cover
  • PCP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Arora, E. Chlamtac, and M. Charikar. New approximation guarantee for chromatic number. In Proc. STOC, pages 215-224, 2006. Google Scholar
  2. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Google Scholar
  3. S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Google Scholar
  4. P. Austrin, V. Guruswami, and J. Håstad. (2 + ε)-sat is NP-hard. In Proc. FOCS, pages 1-10, 2014. Google Scholar
  5. N. Bansal. Constructive algorithms for discrepancy minimization. In Proc. FOCS, pages 3-10, 2010. Google Scholar
  6. A. Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470-516, 1994. Google Scholar
  7. A. Blum and D. R. Karger. An Õ(n^3/14)-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49-53, 1997. Google Scholar
  8. B. Bollobás, D. Pritchard, T. Rothvoß, and A. D. Scott. Cover-decomposition and polychromatic numbers. SIAM Journal on Discrete Mathematics, 27(1):240-256, 2013. Google Scholar
  9. J. Brakensiek and V. Guruswami. The quest for strong inapproximability results with perfect completeness. In Proc. APPROX-RANDOM, pages 4:1-4:20, 2017. URL: https://eccc.weizmann.ac.il/report/2017/080.
  10. M. Charikar, A. Newman, and A. Nikolov. Tight hardness results for minimizing discrepancy. In Proc. SODA, pages 1607-1614, 2011. Google Scholar
  11. H. Chen and A. M. Frieze. Coloring bipartite hypergraphs. In Proc. IPCO, pages 345-358, 1996. Google Scholar
  12. I. Dinur and V. Guruswami. PCPs via low-degree long code and hardness for constrained hypergraph coloring. In Proc. FOCS, 2013. Google Scholar
  13. I. Dinur, O. Regev, and C. D. Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, 2005. Google Scholar
  14. V. Guruswami, J. Håstad, P. Harsha, S. Srinivasan, and G. Varma. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. SIAM Journal of Computing, 46(1):132-159, 2017. Google Scholar
  15. V. Guruswami, J. Håstad, and M. Sudan. Hardness of approximate hypergraph coloring. SIAM Journal of Computing, 31(6):1663-1686, 2002. Google Scholar
  16. V Guruswami and S. Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM Journal of Discrete Mathematics, 18(1):30-40, 2004. Google Scholar
  17. V. Guruswami and E. Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. Electronic Colloquium on Computational Complexity (ECCC), 21:43, 2014. URL: http://eccc.hpi-web.de/report/2014/043.
  18. V. Guruswami and E. Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. In Proc. SODA, pages 822-836, 2015. Google Scholar
  19. V. Guruswami and R. Saket. Hardness of rainbow coloring hypergraphs. Electronic Colloquium on Computational Complexity (ECCC), 2017. URL: https://eccc.weizmann.ac.il/report/2017/147/.
  20. E. Halperin, R. Nathaniel, and U. Zwick. Coloring k-colorable graphs using relatively small palettes. Journal of Algorithms, 45(1):72-90, 2002. Google Scholar
  21. J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  22. J. Holmerin. Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε. In Proc. CCC, 2002. Google Scholar
  23. S. Huang. 2^(log n)^1/10 - o(1) hardness for hypergraph coloring. CoRR, abs/1504.03923, 2015. Google Scholar
  24. D. R. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, 1998. Google Scholar
  25. K. Kawarabayashi and M. Thorup. Combinatorial coloring of 3-colorable graphs. In Proc. FOCS, pages 68-75, 2012. Google Scholar
  26. P. Kelsen, S. Mahajan, and R. Hariharan. Approximate hypergraph coloring. In Proc. SWAT, pages 41-52, 1996. Google Scholar
  27. S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. Combinatorica, 20(3):393-415, 2000. Google Scholar
  28. S. Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. FOCS, pages 23-32, 2002. Google Scholar
  29. S. Khot. On the power of unique 2-prover 1-round games. In Proc. STOC, pages 767-775, 2002. Google Scholar
  30. S. Khot and R. Saket. Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. In Proc. SODA, pages 1607-1625, 2014. Google Scholar
  31. S. Khot and R. Saket. Hardness of coloring 2-colorable 12-uniform hypergraphs with 2^(log n)^Ω(1) colors. SIAM Journal of Computing, 46(1):235-271, 2017. Google Scholar
  32. M. Krivelevich, R. Nathaniel, and B. Sudakov. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms, 41(1):99-113, 2001. Google Scholar
  33. S. Lovett and R. Meka. Constructive discrepancy minimization by walking on the edges. SIAM Journal of Computing, 44(5):1573-1582, 2015. Google Scholar
  34. E. Mossel. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19:1713-1756, 2010. Google Scholar
  35. E. Mossel, K. Oleszkiewicz, and A. Sen. On reverse hypercontractivity. Geometric and Functional Analysis, 23(3):1062-1097, 2013. Google Scholar
  36. R. Raz. A parallel repetition theorem. SIAM Journal of Computing, 27(3):763-803, 1998. Google Scholar
  37. R. Saket. Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs. In Proc. CCC, pages 78-89, 2014. Google Scholar
  38. G. Varma. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Chicago J. Theor. Comput. Sci., 2016, 2016. Google Scholar
  39. A. Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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