The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
Venkatesan Guruswami, Ali Kemal Sinop · 2011
We prove almost tight hardness results under randomized reductions for finding independent sets in bounded degree graphs and hypergraphs that admit a good coloring. Our specific results include the following (where Δ, a constant, is a bound on the degree, and n is the number of vertices): NP-hardness of finding an independent set of size larger than in a 2-colorable r-uniform hypergraph for each fixed r ≥ 4. A simple algorithm is known to find independent sets of size in any r-uniform hypergraph of maximum degree Δ. Under a combinatorial conjecture on hypergraphs, the (log Δ)1/(r–1) factor in our result is necessary. Conditional hardness of finding an independent set with more than vertices in a k-colorable (with k ≥ 7) graph for some absolute constant c ≤ 4, under Khot's 2-to-1 Conjecture. This suggests the near-optimality of Karger, Motwani and Sudan's graph coloring algorithm which finds an independent set of size in k-colorable graphs. Conditional hardness of finding independent sets of size in almost 2-colorable 3-uniform hypergraphs, under Khot's Unique Games Conjecture. This suggests the optimality of the known algorithms to find an independent set of size in 2-colorable 3-uniform hypergraphs. Conditional hardness of finding an independent set of size more than in r-uniform hypergraphs that contain an independent set of size n(1 − O (log r/r)) assuming the Unique Games Conjecture.