TR10-111 Authors: Venkatesan Guruswami, Ali Kemal Sinop

Publication: 14th July 2010 23:56

Downloads: 2919

Keywords:

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good

coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and

$n$ is the number of vertices):

\begin{itemize}

\item {\em 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 a $2$-colorable $r-uniform hypergraph for $r \ge 4$. A simple algorithm is known to find

independent sets of size

$\Omega\left(\frac{n}{\Delta^{1/(r-1)}}\right)$ in {\em 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.

\item 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 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.

\item Conditional hardness of finding independent sets of size $n \Delta^{-1/8+o_\Delta(1)}$ in almost $2$-colorable

$3$-uniform hypergraphs, under the 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.

\item Conditional hardness of finding an independent set of size more than

$O\left(n \left( \frac{\log \Delta}{\Delta}

\right)^{\frac{1}{r-1}}\right)$

in $r$-uniform hypergraphs that contain an independent set of size

$n \Bigl(1-O\bigl(\frac{\log r}{r}\bigr)\Bigr)$ assuming the Unique

Games Conjecture.

\end{itemize}