Conditional hardness for approximate coloring

DOI10.1145/1132516.1132567MaRDI QIDQ2931398zbMATH OpenOpenAlexFDO

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)

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

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)

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].

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

Cited in

(17)

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

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)