TY - GEN
T1 - New tools for graph coloring
AU - Arora, Sanjeev
AU - Ge, Rong
N1 - Funding Information:
Research supported by NSF Grants CCF-0832797, 0830673, and 0528414.
PY - 2011
Y1 - 2011
N2 - 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 nO(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 2O(Δ) 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.
AB - 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 nO(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 2O(Δ) 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.
UR - http://www.scopus.com/inward/record.url?scp=80052390333&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052390333&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22935-0_1
DO - 10.1007/978-3-642-22935-0_1
M3 - Conference contribution
AN - SCOPUS:80052390333
SN - 9783642229343
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
Y2 - 17 August 2011 through 19 August 2011
ER -