Approximate Graph Coloring by Semidefinite Programming

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We give a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with min {O(/spl Delta//sup 1/3/log/sup 4/3//spl Delta/), O(n/sup 1/4/ log n)} colors where /spl Delta/ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree /spl Delta/. This result can be generalized to k-colorable graphs to obtain a coloring using min {O/spl tilde/(/spl Delta//sup 1-2/k/), O/spl tilde/(n/sup 1-3/(k+1/))} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz /spl thetav/-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the /spl thetav/-function. >

Authors

• David R. Karger
• Rajeev Motwani 0001
• Madhu Sudan 0001

Keywords

• Law
• Legal factors
• Approximation algorithms
• Polynomials
• Computer science
• Scheduling
• Algorithm design and analysis
• Greedy algorithms
• Semidefinite Programming
• Conjecture
• Collection Of Sets
• Number Of Graphs
• Linear Programming
• Feasible Solution
• Maximum Degree
• Polynomial-time Algorithm
• Adjacent Vertices
• Current Address
• Bell Labs
• Linear Programming Relaxation
• Color Assignment
• Normal Distribution
• Analysis Steps
• Unit Vector
• Normality Of Variance
• Probability Of Events
• Exponential Distribution
• Standard Normal Distribution
• Components Of Vector
• Random Vector
• Standard Normal Variate
• N-dimensional Vector
• Dot Product
• Vector Of Length
• Independent Random Variables
• Choice Of Distribution
• Induced Subgraph
• Previous Lemma
• Spherically Symmetric