Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR10-111 | 14th July 2010 23:55

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

TR10-111
Authors: Venkatesan Guruswami, Ali Kemal Sinop
Publication: 14th July 2010 23:56
Keywords:

Abstract:

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}

ISSN 1433-8092 | Imprint