Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

DOI10.1137/1.9781611973730.56zbMath1371.68208OpenAlexW2403162531MaRDI QIDQ5363095

Euiwoong Lee, Venkatesan Guruswami

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.56

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

$(2+\varepsilon)$-Sat Is NP-hard ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Hardness of Rainbow Coloring Hypergraphs

This page was built for publication: Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs