Conditional hardness for approximate coloring

DOI10.1145/1132516.1132567zbMATH Open1301.68143arXivcs/0504062OpenAlexW2004804919MaRDI QIDQ2931398FDOQ2931398

Authors: Irit Dinur, Elchanan Mossel, Oded Regev 

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We study the coloring problem: Given a graph G, decide whether $c(G)leqq$ or $c(G)geQ$, where c(G) is the chromatic number of G. We derive conditional hardness for this problem for any constant $3leq<Q$. For $qge4$, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For $q=3$, we base our hardness result on a certain `fish shaped' variant of his conjecture. We also prove that the problem almost coloring is hard for any constant $eps>0$, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a $eps$ fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least $eps$. Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

Full work available at URL: https://arxiv.org/abs/cs/0504062

Recommendations

• Conditional Hardness for Approximate Coloring
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Improved hardness of approximating chromatic number
• On the hardness of approximating the chromatic number

zbMATH Keywords

graph coloringhardness of approximationunique games conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (17)

• Title not available (Why is that?)
• Deciding Relaxed Two-Colourability: A Hardness Jump
• New tools for graph coloring
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Two generalizations of proper coloring: hardness and approximability
• New hardness results for graph and hypergraph colorings
• A simple algorithm for 4-coloring 3-colorable planar graphs
• On the tractability of coloring semirandom graphs
• A note on unique games
• Noise stability of functions with low influences: invariance and optimality
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Gaussian bounds for noise correlation of functions
• Maximally stable Gaussian partitions with discrete applications
• Robust optimality of Gaussian noise stability
• Conditional Hardness for Approximate Coloring
• A quantitative Arrow theorem

This page was built for publication: Conditional hardness for approximate coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931398)