Deterministic algorithm approximates large independent sets in graphs
Approximating Independent Sets Using Additive Combinatorics
Data Structures and AlgorithmsComputational Complexity
Summary
Finding a largest independent set in a graph means picking the biggest group of nodes with no connections between them. This problem is usually very hard to solve exactly. The authors present a new method that can quickly find an approximate solution, getting close to the size of the largest set if it’s big enough. Their approach uses ideas from a branch of math called additive combinatorics to find useful structures in the graph, then extracts the independent set efficiently.
What this means in practice
- •For network schedulers: Find large conflict-free sets of tasks or resources more efficiently when task dependencies form large independent sets.
- •For compiler engineers: Improve register allocation by approximating large independent sets in interference graphs within feasible running time.
A theory result. No direct application yet.
Authors
Shachar Lovett
Abstract
We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.