cs.CC — Computational Complexity

The Esperanza Algorithm for Maximum Independent Set

Contributed by Frank Vega

The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within $n^{1-\varepsilon}$ for every $\varepsilon>0$, and under the Unique Games Conjecture it is hard to approximate within $O(\Delta/\log^2\Delta)$ on graphs of maximum degree $\Delta$; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a $(2-\varepsilon)$-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising $(k,k+1)$-improvements, and an iterated $(1,2)$-swap search. We prove that it runs in $O((n+m)\,\alpha_{\mathrm A}(n))$ expected time for fixed budgets, with $\alpha_{\mathrm A}$ the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most $2\tau-r$ vertices, where $\tau$ is the minimum cover size and $r$ the number of components with an edge, and that the ratio is at most $(\Delta+2)/3$ on graphs of maximum degree $\Delta$. We prove the ratio $2\sqrt n$ on every graph with $\Delta\le\sqrt n$ and on three further classes, and state it for all graphs as a conjecture, whose proof would imply $\mathrm{P}=\mathrm{NP}$. We also state the conjecture that the complementary cover has at most $2\tau-|M|$ vertices for the NetworkX minimum maximal matching $M$; a proof would give a $3/2$-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless $\mathrm{P}=\mathrm{NP}$. In reproducible experiments the returned set is optimal on all $30\,000$ graphs of a suite certified by an exact integer program; on $40$ Khot--Regev YES instances with $640$ to $2\,560$ vertices the conjectured bound is certified on $38$ and open on $2$; and on $31$ bounded-degree graphs the certified ratio is at most $1.0769$ on the families with a planted independent set.