An Approximate Independent Set Solver: The Esperanza Algorithm

Source abstract

The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph and is NP-hard in general. This paper describes Esperanza, an approximation algorithm that runs in $O(n + m)$ time on a graph with $n$ vertices and $m$ edges. The starting point is a small observation about the bipartite double cover of the input graph: its maximum cut is trivially exact, and the freedom left in choosing that cut, namely flipping whole components, can be spent so that one side of the assignment becomes as small as possible. Projecting the opposite, large side back onto the original vertex set produces a generous candidate solution. The candidate is then repaired: on every edge whose two endpoints both survive in the candidate, the endpoint carrying more conflicts is deleted, with conflict counters updated on the fly. A final pass grows the repaired set into a maximal independent set, taking vertices in increasing order of degree. We prove that the output is always a maximal independent set and that on bipartite graphs its size is at least half the independence number, which gives a ratio of $2$ there. Beyond the bipartite case we prove nothing about the ratio, and we say so plainly. What we offer instead is evidence. In experiments where every optimum was certified by integer programming, a reproducible run over $30{,}000$ instances never produced a ratio above $2$ (the mean was $1.049$), and the worst ratio we have ever seen is $2.5$, on a small hand-crafted instance whose ratio survives, without growing, two natural amplification constructions. We conjecture that the approximation ratio is bounded by a universal constant, keep $5/2$ only as the current record, examine how each family of graphs behaves relative to the conjectured bound, and sketch linear-time modifications that would eliminate every worst case we know of.