The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Jan 19, 2011

ABSTRACT:
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 $\Delta$, 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 $O\left(n \left( \frac{\log \Delta}{\Delta}\right)^{\frac{1}{r-1}}\right)$ in 2-colorable r-uniform hypergraph for each fixed $r \ge 4$. A simple algorithmis known to find independent sets of size $\Omega\left(\frac{n}{\Delta^{1/(r-1)}}\right)$ in any $r$-uniform hypergraph of maximum degree $\Delta$. Under a combinatorial conjecture on hypergraphs, the $(\log\Delta)^{1/(r-1)}$ factor in our result is necessary.

-- Conditional hardness of finding an independent set with more than $O\left(\frac{n}{\Delta^{1-c/(k-1)}}\right)$ vertices in a $k$-colorable (with $k\ge 7$) graph for some absolute constant $c \le 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 $\Omega\left(\frac{n}{\Delta^{1-2/k}\sqrt{\log \Delta}}\right)$ in k-colorable graphs.

-- Conditional hardness of finding independent sets of size $n \Delta^{-1/8+o_\Delta(1)}$ 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 $\tilde{\Omega}(n \Delta^{-1/8})$ in $2$-colorable $3$-uniform hypergraphs.

-- Conditional hardness of finding an independent set of size more than $O\big(n \Delta^{-\frac{1}{r-1}} \log^{\frac{1}{r-1}}\Delta \big)$ in $r$-uniform hypergraphs that contain an independent set of size $n \big(1-O(\log r/r)\big)$ assuming the Unique Games Conjecture.

-- NP-hardness of finding an independent set of size larger than $O\left(n \left( \frac{\log \Delta}{\Delta}\right)^{\frac{1}{r-1}}\right)$ in 2-colorable r-uniform hypergraph for each fixed $r \ge 4$. A simple algorithmis known to find independent sets of size $\Omega\left(\frac{n}{\Delta^{1/(r-1)}}\right)$ in any $r$-uniform hypergraph of maximum degree $\Delta$. Under a combinatorial conjecture on hypergraphs, the $(\log\Delta)^{1/(r-1)}$ factor in our result is necessary.

-- Conditional hardness of finding an independent set with more than $O\left(\frac{n}{\Delta^{1-c/(k-1)}}\right)$ vertices in a $k$-colorable (with $k\ge 7$) graph for some absolute constant $c \le 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 $\Omega\left(\frac{n}{\Delta^{1-2/k}\sqrt{\log \Delta}}\right)$ in k-colorable graphs.

-- Conditional hardness of finding independent sets of size $n \Delta^{-1/8+o_\Delta(1)}$ 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 $\tilde{\Omega}(n \Delta^{-1/8})$ in $2$-colorable $3$-uniform hypergraphs.

-- Conditional hardness of finding an independent set of size more than $O\big(n \Delta^{-\frac{1}{r-1}} \log^{\frac{1}{r-1}}\Delta \big)$ in $r$-uniform hypergraphs that contain an independent set of size $n \big(1-O(\log r/r)\big)$ assuming the Unique Games Conjecture.