Improved Inapproximability Results for Maximum $k$-Colorable Subgraph

April 29, 2009

We study the maximization version of the fundamental graph coloring
problem. Here the goal is to color the vertices of a $k$-colorable
graph with $k$ colors so that a maximum fraction of edges are
properly colored (i.e. their endpoints receive different colors). A
random $k$-coloring properly colors an expected fraction
$1-\frac{1}{k}$ of edges. We prove that given a graph promised to be
$k$-colorable, it is NP-hard to find a $k$-coloring that properly
colors more than a fraction $\approx 1-\frac{1}{33 k}$
of edges. Previously, only a hardness factor
of $1- O({1}/{k^2})$ was known. Our result pins down
the correct asymptotic dependence of the approximation factor on
$k$. Along the way, we prove that approximating the Maximum
$3$-colorable subgraph problem within a factor greater than $\frac{32}{33}$
is NP-hard.
Using semidefinite programming, it is known that one can do better
than a random coloring and properly color a fraction $1-\frac{1}{k}
+\frac{2 \ln k}{k^2}$ of edges in polynomial time. We show that,
assuming the $2$-to-$1$ conjecture, it is hard to properly color
(using $k$ colors) more than a fraction $1-\frac{1}{k} + O\left(\frac{\ln
k}{k^2}\right)$ of edges of a
$k$-colorable graph.

Joint work with Venkatesan Guruswami.

Joint work with Venkatesan Guruswami.