Document Open Access Logo

Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

Authors Venkatesan Guruswami, Sai Sandeep

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.15.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Carnegie Mellon University, Pittsburgh, PA, USA
Sai Sandeep
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

Research supported in part by NSF grants CCF-1422045, CCF-1526092, and CCF-1814603.

Acknowledgements

We thank Amey Bhangale, Joshua Brakensiek, Jakub Opršal, and Xinyu Wu for useful discussions. We would also like to thank anonymous reviewers for helpful comments.

Cite AsGet BibTex

Venkatesan Guruswami and Sai Sandeep. Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.15

Abstract

A k-uniform hypergraph is said to be r-rainbow colorable if there is an r-coloring of its vertices such that every hyperedge intersects all r color classes. Given as input such a hypergraph, finding a r-rainbow coloring of it is NP-hard for all k >= 3 and r >= 2. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When r=k (the maximum possible value), i.e., the hypergraph is k-partite, one can efficiently 2-rainbow color the hypergraph, i.e., 2-color its vertices so that there are no monochromatic edges. In this work we consider the next smaller value of r=k-1, and prove that in this case it is NP-hard to rainbow color the hypergraph with q := ceil[(k-2)/2] colors. In particular, for k <=6, it is NP-hard to 2-color (k-1)-rainbow colorable k-uniform hypergraphs. Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set [r]^n. We prove that any such polymorphism f: [r]^n -> [q] must be C-fixing, i.e., there is a small subset S of C coordinates and a setting a in [q]^S such that fixing x_{|S} = a determines the value of f(x). The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the C-fixing characterization, our NP-hardness is obtained via a reduction from smooth Label Cover.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • inapproximability
  • hardness of approximation
  • constraint satisfaction
  • hypergraph coloring
  • polymorphisms

Metrics

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

Related Versions

References

  1. Andris Ambainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Sensitivity Versus Certificate Complexity of Boolean Functions. In Proceedings of the 11th International Computer Science Symposium on Computer Science - Theory and Applications - Volume 9691, CSR 2016, pages 16-28, 2016. URL: https://doi.org/10.1007/978-3-319-34171-2_2.
  2. Per Austrin, Amey Bhangale, and Aditya Potukuchi. Improved Inapproximability of Rainbow Coloring. CoRR, abs/1810.02784, 2018. Google Scholar
  3. Per Austrin, Amey Bhangale, and Aditya Potukuchi. Simplified inpproximability of hypergraph coloring via t-agreeing families. CoRR, abs/1904.01163, 2019. URL: http://arxiv.org/abs/1904.01163.
  4. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat Is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  5. Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, pages 250-261, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_22.
  6. Amey Bhangale. NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. In 45th International Colloquium on Automata, Languages, and Programming, pages 15:1-15:11, 2018. Google Scholar
  7. Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 152-174, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.152.
  8. Joshua Brakensiek and Venkatesan Guruswami. New Hardness Results for Graph and Hypergraph Colorings. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 14:1-14:27, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.14.
  9. Joshua Brakensiek and Venkatesan Guruswami. The Quest for Strong Inapproximability Results with Perfect Completeness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 4:1-4:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.4.
  10. Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1782-1801, 2018. URL: https://doi.org/10.1137/1.9781611975031.117.
  11. Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  12. Jakub Bulín, Andrei A. Krokhin, and Jakub Oprsal. Algebraic approach to promise constraint satisfaction. CoRR, abs/1811.00970, 2018. STOC 2019, to appear. URL: http://arxiv.org/abs/1811.00970.
  13. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional Hardness for Approximate Coloring. SIAM J. Comput., 39(3):843-873, 2009. Google Scholar
  14. Irit Dinur, Oded Regev, and Clifford D. Smyth. The Hardness of 3-Uniform Hypergraph Coloring. Combinatorica, 25(5):519-535, 2005. URL: https://doi.org/10.1007/s00493-005-0032-4.
  15. Venkatesan Guruswami, Johan Håstad, and Madhu Sudan. Hardness of Approximate Hypergraph Coloring. SIAM J. Comput., 31(6):1663-1686, 2002. URL: https://doi.org/10.1137/S0097539700377165.
  16. Venkatesan Guruswami and Euiwoong Lee. Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Combinatorica, 38(3):547-599, 2018. URL: https://doi.org/10.1007/s00493-016-3383-0.
  17. 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, December 11-15, 2017, Kanpur, India, pages 33:33-33:15, 2017. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.33.
  18. Venkatesan Guruswami and Sai Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms. Electronic Colloquium on Computational Complexity (ECCC), 2019. URL: https://eccc.weizmann.ac.il/report/2019/094/.
  19. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: https://doi.org/10.1145/502090.502098.
  20. Jonas Holmerin. Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 544-552, 2002. Google Scholar
  21. Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.00847.
  22. Subhash Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 23-32. IEEE, 2002. Google Scholar
  23. Subhash Khot and Rishi Saket. Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1607-1625, 2014. Google Scholar
  24. Andrei A. Krokhin and Jakub Oprsal. The complexity of 3-colouring H-colourable graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.03214.
  25. Miklós Maróti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra universalis, 59(3):463-489, December 2008. URL: https://doi.org/10.1007/s00012-008-2122-9.
  26. Colin McDiarmid. A Random Recolouring Method for Graphs and Hypergraphs. Combinatorics, Probability and Computing, 2(3):363–365, 1993. URL: https://doi.org/10.1017/S0963548300000730.
  27. Elchanan Mossel. Gaussian Bounds for Noise Correlation of Functions. Geometric and Functional Analysis, 19:1713–1756, 2010. Google Scholar
  28. Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics, 171:295–341, 2010. Google Scholar
  29. N. Nisan. CREW PRAMs and decision trees. In Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC '89, pages 327-335. ACM, 1989. URL: https://doi.org/10.1145/73007.73038.
  30. Sushant Sachdeva and Rishi Saket. Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 219-229, 2013. URL: https://doi.org/10.1109/CCC.2013.30.
  31. Rishi Saket. Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs. In Proceedings of the 29th IEEE Conference on Computational Complexity, pages 78-89, 2014. Google Scholar
  32. Hans-Ulrich Simon. A tight Ω(loglog n)-bound on the time for parallel RAMs to compute nondegenerated boolean functions. In Foundations of Computation Theory, pages 439-444. Springer Berlin Heidelberg, 1983. Google Scholar
  33. Cenny Wenner. Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four. Theory of Computing, 9(23):703-757, 2013. Google Scholar
  34. Marcin Wrochna and Stanislav Zivny. Improved hardness for H-colourings of G-colourable graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.00872.
  35. Dmitriy Zhuk. A Proof of CSP Dichotomy Conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
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 Imprint Privacy Contact