Deterministic quasi polynomial time improves max independent set approximation
Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
Data Structures and AlgorithmsComputational Complexity
Summary
Finding the largest independent set in a graph (a set of points with no connections between them) is a tough problem. The authors provide a new algorithm that runs in quasi-polynomial time to find larger independent sets than previous methods could in similar time. Their approach improves on past guarantees by allowing better approximations for certain graph sizes. However, there are known theoretical limits that prevent this method from improving beyond a certain point. So, their technique pushes the boundary but also respects fundamental barriers in the problem's complexity.
What this means in practice
- •For network schedulers: Improve scheduling algorithms by better approximating conflict-free sets in large communication networks where independent sets represent non-interfering tasks.
- •For resource allocation teams: Enhance resource assignment methods in distributed systems by using more efficient approximations of maximal independent sets to reduce conflicts.
A theory result. No direct application yet.
Authors
Zhao Song
Abstract
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^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\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α(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}$.