Source-linked AI summary
Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
Zhao Song
TL;DR
The paper studies approximation of maximum independent set and presents a deterministic quasi-polynomial-time algorithm. It gives an independent set of size at least 2^t when α(G) ≥ 2^-tN, for 1 ≤ t ≤ √log N/12. This yields an approximation ratio of N/2^Ω(√log N), while integrality gaps bound the range of a related universal Lasserre-value analysis.
Problem
The paper addresses the gap between approximation algorithms and hardness for maximum independent set, including the prior quasi-polynomial-time guarantee of N/2^Ω((log N)^(1/3)).
Source: §1 · p. 2, §1.1 · p. 3Method
A deterministic algorithm constructs a pseudo-distribution and uses a large sparse set to obtain an independent set under the stated promise.
Source: §4.4 · p. 12, §4.5 · p. 15Results
For 1 ≤ t ≤ √log N/12, the algorithm finds an independent set of size at least 2^t when α(G) ≥ 2^-tN, in time N^O(t).
Source: §1.1 · p. 3Takeaways & Limitations
The deterministic quasi-polynomial-time approximation ratio improves from N/2^Ω((log N)^(1/3)) to N/2^Ω(√log N).
Source: §1.1 · p. 3At 2^o(√(log N log log N)) levels, a universal implication from the Lasserre value to independent-set existence cannot extend beyond t = O(√(log N log log N)); this does not rule out algorithms using additional graph properties.
Source: §1.1 · p. 3, §4.7 · pp. 17, 19
Abstract
from arXiv · showhide
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{\Omega(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{\Omega((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrow\alpha(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.
1 Introduction
The paper gives a deterministic quasi-polynomial-time algorithm for maximum independent set, improving the prior approximation ratio of N/2^Ω((log N)^(1/3)) to N/2^Ω(√log N). Its Lasserre-based analysis has a limit for universal implications, as indicated by Tulsiani’s integrality gaps.
1 Introduction
- Classical polynomial-time algorithms achieve O(N(log log N)^2/(log N)^3), but assuming P ≠ NP, polynomial time cannot give a fixed polynomial saving over N.The earlier Boppana–Halldórsson and Feige bounds improve only polylogarithmically on the trivial ratio.Source: §1 · p. 2
- Quasi-polynomial time permits finer approximation ratios: enumeration gives O(N/(log N)^a), while Khot and Ponnuswami establish hardness at N/2^((log N)^(3/4+ϵ)) under their stated assumption [KP06].Source: §1 · p. 2
1.1 Our result
- Tulsiani’s integrality gaps limit universal implications from Lasserre values to independent-set existence at 2^o(√(log N log log N)) levels.The stated limitation applies to this form of implication, not to every algorithmic approach.Source: §1 · p. 2, §1.1 · p. 3
- For 1 ≤ t ≤ √log N/12, the algorithm turns α(G) ≥ 2^-tN into an independent set of size at least 2^t in time N^O(t).Consequently, it achieves an approximation ratio of N/2^Ω(√log N) in deterministic time N^O(√log N).Source: §1.1 · p. 3
- The deterministic quasi-polynomial-time approximation improves from N/2^Ω((log N)^(1/3)) to N/2^Ω(√log N), advancing Lovett’s open problem [Lov26, Section 1.3].Source: §1.1 · p. 3
2 Technique Overview
The overview contrasts Lovett’s conditioning-and-enumeration approach with two changes that improve its sparse-set bound. These changes yield an independent set of size at least 2^t under the stated promise and parameter range.
2.1 Lovett’s Method
- Lovett’s method starts from a pseudo-distribution with objective at least 2^−tN, then thresholds marginals to form an initial vertex set.The initial threshold is 2^−(t+1), and the resulting set has size at least that threshold times N.Source: §2.1 · p. 3
- Under the iteration described, fewer than 2(t + 1) conditioning steps suffice, yielding a vertex set U with |U| ≥ 2^−O(t^2h)N and edge density d(U) ≤ 2^−h.Source: §2.1 · p. 4
- Lovett enumerates conditioning sets of size O(t), keeps candidates whose conditioned marginals exceed a threshold, and applies greedy extraction.The extraction bound gives an independent set of size at least 2^t.Source: §2.1 · p. 4
2.2 Our Techniques
- Selecting a dyadic correlation scale and charging vertex loss to marginal gain improve the sparse-set exponent from O(t^2h) to O(th).Steps 1 and 5 remain unchanged, while Step 4 adapts enumeration to variable thresholds.Source: §2.2 · p. 4
- The revised correlation step tracks dyadic classes with geometric weights, avoiding a loss that depends on the number of scales.A class with sufficient weighted contribution supplies a vertex and subset with increased conditioned marginals.Source: §2.2 · pp. 4–5
- The revised iteration charges each deleted vertex to marginal growth, retaining at least 2^−O(th)N vertices after O(t) conditioning steps.The resulting size bound is combined with the unchanged greedy extraction step.Source: §2.2 · p. 5
- Enumeration adapts to variable thresholds by enumerating both the conditioning set and a vertex whose marginal identifies the desired set.For h = O(t), this preserves the N^O(t) running time.Source: §2.2 · p. 5
- For t ≤ √log N/12, the improved sparse-set bound yields an independent set of size at least 2^t and approximation ratio N/2^Ω(√log N) in quasi-polynomial time.The proof establishes |U| ≥ 2^t+1 before greedy extraction.Source: §2.2 · p. 5
3 Preliminaries
The preliminaries define pseudo-distributions and their conditioning, then develop covariance and greedy bounds used to find large independent sets. They also specify notation for edge density and matrix operations.
3 Preliminaries
- The paper uses d(U) for edge density, defines Vk as vertex subsets of size at most k, and uses ⪯ for positive-semidefinite matrix order.Logarithms are base 2, and ◦ denotes the Hadamard product.Source: §3 · p. 5
- A level-r pseudo-distribution assigns marginals to vertex sets up to size 2r, vanishes on sets containing an edge, and satisfies positivity constraints.Singleton marginals lie in [0,1], and adjacent vertices have zero joint marginal.Source: §3 · p. 6
- Conditioning on a set with positive marginal preserves pseudo-distribution feasibility while reducing the available level by the set’s size.Successive conditioning obeys the marginal identity stated for adding a vertex.Source: §3 · pp. 6–7
- The normalized covariance matrix is positive semidefinite, and its entrywise powers have nonnegative sums; odd powers force positive correlations to offset edge contributions.The argument uses the Schur product theorem and the all-ones vector.Source: §3 · pp. 7–8
- The minimum-degree greedy algorithm returns an independent set of size at least n/(1 + 2|E(H)|/n).The proof bounds the number of rounds using a potential based on reciprocal degrees and Jensen’s inequality.Source: §3 · p. 8
4 Proof of the main theorem
This section develops the proof techniques for constructing a large sparse vertex set and deterministically obtaining the stated independent-set guarantee and approximation. It also shows that, under subexponential level bounds, a universal implication from Lasserre values cannot extend much beyond the stated parameter range.
4.1 Dyadic increment
- Conditioning on a suitable vertex raises marginals for a subset whose size is controlled by the dyadic correlation scale.The dyadic increment lemma selects a correlation class and vertex to obtain the increase.Source: §4.1 · pp. 8–10
4.2 Cost per bit
- The cost-per-bit bound controls logarithmic loss in retained-set size by logarithmic increase in the marginal threshold, uniformly across dyadic correlation scales.The bound applies for every integer correlation-scale index j ≥ −1.Source: §4.2 · p. 10
4.3 Iterated conditioning
- At most 2t+1 conditioning steps yield a positive-mass set S and threshold τ in [2^-(t+1), 1], retaining at least 2^-(K+1)(t+1)N vertices at density ≤ 2^-h.The construction terminates when the retained set reaches the target density.Source: §4.3 · pp. 10, 12
4.4 Computing a pseudo-distribution
- In N^{O(r)} time, the algorithm outputs a rational level-r pseudo-distribution whose total marginal mass is at least half the promised independent-set lower bound.The guarantee applies when α(G) ≥ 2^-tN.Source: §4.4 · pp. 12, 15
4.5 Finding a large sparse set
- Given α(G) ≥ 2^-tN, deterministic enumeration finds a nonempty U inducing a sparse subgraph of the required size in N^{O(t)} + O(log(h + 1)) time.The search enumerates small conditioning sets and marginal thresholds.Source: §4.5 · p. 15
- The sparse-set argument produces U with |U| ≥ 2^-O(th)N and d(U) ≤ 2^-h.The proof uses a candidate set whose size and density meet these bounds.Source: §4.5 · p. 15
4.6 Completing the proof of the main theorem
- For 1 ≤ t ≤ √log N/12, if α(G) ≥ 2^-tN, a deterministic algorithm finds an independent set of size at least 2^t in time N^O(t).Source: §4.6 · p. 16
- In time N^O(√log N), a deterministic algorithm outputs an independent set of size at least α(G)2^T/N, where T = ⌊√log N/12⌋.The guarantee holds whether or not α(G) ≥ 2^-T N.Source: §4.6 · pp. 16–17
4.7 A Limitation of the Analysis
- The proof’s dependence on α(G) ≥ 2^-tN is through the pseudo-distribution computed in Lemma 4.4, so the same argument applies using the Lasserre value.The proof approximates Las_{2t+5}(G) from below to additive error 1/2.Source: §4.7 · p. 17
- Under a uniform subexponential bound on the number of Lasserre levels, no universal implication can cover tmax(N) = ω(√log N log log N) for all sufficiently large N.The limitation follows from Tulsiani’s integrality-gap theorem [Tul09]; it does not rule out algorithms using additional graph properties.Source: §4.7 · p. 19