2011 | OriginalPaper | Buchkapitel
New Tools for Graph Coloring
verfasst von : Sanjeev Arora, Rong Ge
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
How to color 3 colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses
n
0.2072
colors. There are no indications that coloring using say
O
(log
n
) colors is hard. It has been suggested that SDP hierarchies could be used to design algorithms that use
n
ε
colors for arbitrarily small
ε
> 0.
We explore this possibility in this paper and find some cause for optimism. While the case of general graphs is till open, we can analyse the Lasserre relaxation for two interesting families of graphs.
For graphs with low
threshold rank
(a class of graphs identified in the recent paper of Arora, Barak and Steurer on the unique games problem), Lasserre relaxations can be used to find an independent set of size Ω(
n
) (i.e., progress towards a coloring with
O
(log
n
) colors) in
n
O
(
D
)
time, where
D
is the threshold rank of the graph. This algorithm is inspired by recent work of Barak, Raghavendra, and Steurer on using Lasserre Hierarchy for unique games. The algorithm can also be used to show that known integrality gap instances for SDP relaxations like
strict vector chromatic number
cannot survive a few rounds of Lasserre lifting, which also seems reason for optimism.
For
distance transitive
graphs of diameter Δ, we can show how to color them using
O
(log
n
) colors in
$n^{2^{O(\Delta)}}$
time. This family is interesting because the family of graphs of diameter
O
(1/
ε
) is easily seen to be
complete
for coloring with
n
ε
colors. The distance-transitive property implies that the graph “looks” the same in all neighborhoods.
The full version of this paper can be found at:
http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf
.