2026-07-21T12:47:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9019 2024-03-06T10:43:10Z ddc:004 open_access

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors Bhangale, Amey Hypergraph coloring Inapproximability Schrijver graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amey Bhangale 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.15 urn:nbn:de:0030-drops-90190 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode