PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates

Ijay Narang, Yukai Tang

arXiv:2609.33684v1cs.DScs.DM

TL;DR

Coloring 3-colorable graphs with few colors is difficult because recovering a 3-coloring is NP-hard. This paper recursively propagates Gaussian certificates through higher-level neighborhoods and uses a bounded, increasing potential to rule out failure of SDP rounding. It gives an improved randomized polynomial-time coloring guarantee and concludes that the rounding must produce a sufficiently large independent set.

  • Problem

    The paper asks how few colors a polynomial-time algorithm can guarantee on graphs promised to be 3-colorable, since recovering a 3-coloring is NP-hard.

    Source: §1 · p. 2

  • Method

    The authors recursively propagate Gaussian certificates along walks through higher-level neighborhoods and use a potential function to rule out failure of KMS′ rounding.

    Source: §1 · p. 2, §1.2 · p. 6

  • Results

    Theorem 1.1 gives a randomized polynomial-time algorithm that, with high probability, properly colors 3-colorable n-vertex graphs with an improved guarantee.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The failure certificates cannot persist through recursive propagation, so KMS′ rounding must return an independent set of the asserted size.

    Source: §1.2 · p. 6

    The analysis assumes a strict vector 3-coloring, and the sparse-regime proof also assumes a maximum-degree bound.

    Source: §1.1 · p. 3, §2.2 · p. 12

Abstract

from arXiv · show

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{\'a}{\v{c}}, 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.

1 Introduction

The paper studies how few colors a polynomial-time algorithm can use on graphs promised to be 3-colorable, and presents an improved guarantee. It extends SDP rounding analysis to higher-level neighborhoods by recursively propagating Gaussian certificates and using a potential function to rule out rounding failure.

1 Introduction

  • Recovering a 3-coloring is NP-hard, and remains NP-hard even when algorithms may use a fixed number of colors.Source: §1 · p. 2

1.1 The Vector 3-Coloring Rounding Framework

  • Earlier SDP approaches used Gaussian rounding with neighborhood methods, while later work examined second- and third-level neighborhoods [KMS98].Source: §1 · p. 2, §1.1 · p. 5

1 Introduction

  • O(n^0.19539) colors was the best previously known guarantee, obtained by Bansal, Huang, and Lee through refined analysis of second- and third-order neighborhoods [BHL26].Source: §1 · p. 2
  • Theorem 1.1 gives a randomized polynomial-time algorithm that, with high probability, properly colors every 3-colorable n-vertex graph with an improved guarantee.The supplied theorem passage does not include the color bound.Source: §1 · p. 2

1.1 The Vector 3-Coloring Rounding Framework

  • The analysis extends neighborhood reasoning to every fixed number of levels, propagating cover structures rather than rounding an improved vector coloring of a higher-level neighborhood.A refined cover-composition lemma supports propagation of recursive Gaussian certificates.Source: §1.1 · p. 5, §1.2 · p. 6

1.2 Outline of our Proof

  • When aggressive KMS′ rounding fails to return enough independent-set vertices, its matching cleanup yields a cover at each vertex of a nonempty induced subgraph.Source: §1.2 · p. 5
  • A potential function compensates for threshold changes caused by root-correlation changes and gains a uniform positive amount per propagation step, contradicting its boundedness.Thus the failure certificate cannot persist, forcing KMS′ to return an independent set of the asserted size.Source: §1.2 · p. 6

2 Recursive Gaussian Certificates

This section develops cover-preserving tools for recursive Gaussian certificates that carry failure of SDP rounding to longer walks. It defines the recursive certificate and gives an extension lemma from level ℓ to level ℓ+1 under specified parameter bounds, using interval selection, projection, and composition.

2.1 Composition of Covers

  • Projection preserves cover structure: projecting an (s, δ)-cover orthogonally to a unit vector yields an (s − ε, δ − 2Φc(ε))-cover.This is presented as a standard lemma, appearing in Chlamtac’s thesis.Source: §2.1 · p. 7
  • The refined cover-composition lemma uses Ehrhard’s inequality and accounts for inner-cover cardinality, enabling a higher threshold than the estimate in.The higher threshold supports a more refined Gaussian-maximum estimate.Source: §2.1 · pp. 7, 11

2.2 Certificates from Longer Walks

  • When condition (i) of Lemma 1.3 fails, alternative (ii) supplies a level-1 recursive Gaussian certificate, which the analysis aims to extend to higher levels.The analysis fixes 0 < c < c†, assumes Δ(G) ≤ n^(3(1+c)/(5+3c)), and chooses t so that Φc(t) = n^(-1/(5+3c)).Source: §2.2 · p. 12
  • A level-2 certificate is constructed by pruning length-2 walks whose types fall in a short interval, and the same construction extends level-ℓ certificates by appending an edge.The level-2 interval has width at most ρt = (log t)^-2.Source: §2.2 · pp. 12, 15
  • Lemma 2.8 extends a level-ℓ recursive Gaussian certificate rooted at i to level ℓ+1, assuming 0 < c < c†, 0 < τ < ν0(c)/2, |a| ≤ L, and 0 ≤ λ ≤ √5 + 3c.The source passage truncates the full certificate parameters and the resulting level-(ℓ+1) parameters.Source: §2.2 · p. 16
  • The extension proof follows the interval selection, projection, and composition steps of Lemma 2.7, with a_new = b2(y) and λ_new = λ2(y) − τ recovering its transition.The proof is deferred to Appendix A.Source: §2.2 · p. 16

3 The Potential Function

The proof uses a potential that rises as recursive Gaussian certificates propagate to higher walk levels, contradicting the bounded feasible region. This rules out the failure subgraph and ensures repeated KMS′ trials return a large independent set with high probability.

3 The Potential Function

  • It suffices to find a certificate with λ > √5 + 3c + Ω(1); the authors achieve this by exhibiting a potential function that increases uniformly at each step.Source: §3 · p. 16

3.1 Motivating the function

  • The threshold coefficient λ need not increase at every step because composition loss and changing normalization can offset its positive contribution.The proof corrects for this by making the potential depend on the correlation.Source: §3.1 · pp. 16–17
  • The candidate potential is derived from a worst-case two-cycle in correlation and verified to satisfy the required inequality for every feasible transition.The motivating cycle has a_new = −a when a^2 ≤ 3c/(1 + 4c).Source: §3.1 · pp. 17–18

3.2 Proof of Theorem 1.5

  • Ruling out the bad subgraph means repeated KMS′ trials yield a large independent set with high probability, in polynomial time when the largest returned set is retained.The trials and retention step complete the algorithmic conclusion.Source: §3.2 · pp. 20–21
  • Unless one recursive step gives an immediate contradiction, each transition raises the potential by more than µ(c)/2, making sufficiently many successive states impossible.The proof chooses the number of steps using the finite potential range on K.Source: §3.2 · p. 21

A Proof of Lemma 2.8

The proof extends a certificate from one walk level to the next by retaining covers with a common edge type and composing projected inner and outer covers. The resulting endpoints form the next recursive Gaussian certificate.

  • Grouping extensions by a common type retains an outer cover while producing a family of inner covers at the next walk level.The common type is selected by partitioning edge directions into intervals and retaining a group with sufficient cover probability.Source: A Proof of Lemma 2.8 · pp. 23–24
  • Projection preserves the inner cover structure, and the retained outer and inner covers are then composed to find a representative endpoint.The composition argument applies the cover lemma to the projected families and obtains an event with probability at least exp(−o(t^2)).Source: A Proof of Lemma 2.8 · pp. 24–25
  • The resulting endpoint set is a recursive Gaussian certificate, with its root correlation determined by the extension geometry.The projected edge direction is orthogonal to the root and intermediate vectors, and the certificate parameters follow from the composed cover.Source: A Proof of Lemma 2.8 · pp. 23, 25

B Proof of Theorem 1.1

The proof combines sparse- and dense-graph progress guarantees to obtain a coloring bound. Choosing parameters with a fixed gap absorbs the polylogarithmic factor in the progress-combination step.

Proof of Theorem 1.1

  • The progress-combination theorem turns progress in either the low-maximum-degree or high-minimum-degree case into a polynomial-time coloring algorithm.The cited theorem combines progress toward an eO(n^α)-coloring across these two degree regimes.Source: B Proof of Theorem 1.1 · p. 26
  • For maximum degree at most n^β(c), Theorem 1.5 gives progress toward an n^α(c)-coloring, while the dense-graph result supplies progress when minimum degree is at least n^β(c).Here β(c) = 3(1 + c)/(5 + 3c) and α(c) = 1/(5 + 3c).Source: B Proof of Theorem 1.1 · p. 26
  • O(n^((13−√97)/18+ε)) colors follow by choosing c below c† and θ between α(c) and (13−√97)/18+ε, then combining sparse and dense progress.The fixed gap between θ and the final exponent absorbs the polylogarithmic factor.Source: B Proof of Theorem 1.1 · p. 26

Related papers

Loading 2609.33684v1…