Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-099 | 16th December 2009 15:18

Improved Inapproximability Results for Maximum k-Colorable Subgraph

RSS-Feed




Revision #1
Authors: Venkatesan Guruswami, Ali Kemal Sinop
Accepted on: 16th December 2009 15:18
Downloads: 1202
Keywords: 


Abstract:

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 $1-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 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.



Changes to previous version:

This is essentially the version that appeared in APPROX 2009, with the conditional hardness result based on the 2-to-1 conjecture. The earlier ECCC version *incorrectly* claimed an extension of the hardness result from d-to-1 conjecture for d larger than 2. This version reverts back to assuming the stronger 2-to-1 conjecture.


Paper:

TR09-099 | 16th October 2009 19:45

Improved Inapproximability Results for Maximum k-Colorable Subgraph





TR09-099
Authors: Venkatesan Guruswami, Ali Kemal Sinop
Publication: 16th October 2009 19:55
Downloads: 1348
Keywords: 


Abstract:

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 $1-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 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 $d$-to-$1$ conjecture, it is hard to properly color (using $k$ colors) more than a fraction $1-1/k+ O(d^{3/2} \ln k/k^2)$ of edges of a $k$-colorable graph.



ISSN 1433-8092 | Imprint