Volume 9 (2013) Article 11 pp. 413-435
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
Revised: February 24, 2013
Published: May 24, 2013
[PDF (402K)]    [PS (1442K)]    [PS.GZ (447K)]
[Source ZIP]
Keywords: hardness of approximation, graph coloring, constraint satisfaction, probabilistically checkable proof
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]


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}{\threehardness k}$ of edges. Previously, only a hardness factor of $1- O\bigl(\frac{1}{k^2}\bigr)$ 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.

An extended abstract of this paper appeared in the Proceedings of the 12th International Workshop on Approximation, Randomization, and Combinatorial Optimization, 2009 (APPROX'09).