Improved Inapproximability Results for Maximum k-Colorable Subgraph

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages, 2 figures

Scientific paper

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-O(1/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 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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Improved Inapproximability Results for Maximum k-Colorable Subgraph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Inapproximability Results for Maximum k-Colorable Subgraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Inapproximability Results for Maximum k-Colorable Subgraph will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-639905

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.