Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs

DOI10.1137/1.9781611973402.117MaRDI QIDQ5384079zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Rishi Saket

Publication date 20 June 2019

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

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fraction of vertices and the incident hyperedges. To be precise, say that a hypergraph is (1-eps)-almost 2-colorable if removing an eps fraction of its vertices and all hyperedges incident on them makes the remaining hypergraph 2-colorable. In particular we prove the following results. For an arbitrarily small constant gamma > 0, there is a constant xi > 0, such that, given a 4-uniform hypergraph on n vertices which is (1 - eps)-almost 2-colorable for eps = 2^{-(log n)^xi}, it is quasi-NP-hard to find an independent set of n/(2^{(log n)^{1-gamma}}) vertices. For any constants eps, delta > 0, given as input a 3-uniform hypergraph on $n$ vertices which is (1-eps)-almost 2-colorable, it is NP-hard to find an independent set of delta n vertices. Assuming the d-to-1 Games Conjecture the following holds. For any constant delta > 0, given a 2-colorable 3-uniform hypergraph on n vertices, it is NP-hard to find an independent set of delta n vertices. The hardness result on independent set in almost 2-colorable 3-uniform hypergraphs was earlier known only assuming the Unique Games Conjecture. In this work we prove the result unconditionally. For independent sets in 2-colorable 3-uniform hypergaphs we prove the first strong hardness result, albeit assuming the d-to-1 Games Conjecture. Our result on almost 2-colorable 4-uniform hypergraphs gives the first nearly polynomial hardness factor for independent set in hypergraphs which are (almost) colorable with constantly many colors. It partially bridges the gap between the previous best lower bound of poly(log n) and the algorithmic upper bounds of n^{Omega(1)}.

Recommendations

• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• The hardness of 3-uniform hypergraph coloring

Cited in

(10)

• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• The quest for strong inapproximability results with perfect completeness
• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
• Hardness of rainbow coloring hypergraphs
• Rainbow coloring hardness via low sensitivity polymorphisms
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• Coloring tournaments with few colors: algorithms and complexity
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring

This page was built for publication: Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs

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