Improved algorithm colors 3-colorable graphs with fewer colors
Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Coloring a graph means assigning colors to points so connected points have different colors. This paper improves a method to color certain graphs that can be colored with just three colors, but where actually finding such a coloring is hard. The authors developed a smarter way to analyze parts of the graph using advanced math involving Gaussian distributions to show their algorithm can color the graph using fewer colors than before, though not as few as three. Their method involves tracking ’failures’ in previous attempts and using that information recursively to get better results.
What this means in practice
- •For network engineers: Assign frequency channels in networks modeled by 3-colorable graphs with fewer channel conflicts using improved coloring algorithms.
- •For compiler developers: Optimize register allocation in compilers for programs modeled by 3-colorable interference graphs, reducing register usage with better coloring.
A theory result. No direct application yet.
Authors
Ijay Narang, Yukai Tang
Abstract
We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamt{á}{č}, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.