Theory of Computing
-------------------
Title : Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
Authors : Venkatesan Guruswami and Ali Kemal Sinop
Volume : 9
Number : 11
Pages : 413-435
URL : https://theoryofcomputing.org/articles/v009a011
Abstract
--------
$ \newcommand{\E}{\mathbb{E}}%_{#1}\left[#2\right]}
\newcommand{\expct}[2]{\mathbb{E}_{#1}\left[#2\right]}
\newcommand{\prob}[2]{\mathsf{Pr}_{#1}\left[#2\right]}
\newcommand{\var}[2]{\mathsf{Var}_{#1}\left[#2\right]}
\newcommand{\cov}[1]{\mathsf{Cov}\left[#1\right]}
\newcommand{\threehardness}{33}
$
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- 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- 1/(33k)$ 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 $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- 1/k + (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- 1/k + O(\ln k/k^2)$
of edges of a $k$-colorable graph.
An extended abstract of this paper appeared in the Proceedings of the
12th International Workshop on Approximation, Randomization, and
Combinatorial Optimization, 2009.