Esperanza: Feasible Guaranteed Approximation for Maximum Independent Set

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 (v0.0.9), an approximation algorithm built around the linear-time Hvala vertex cover approximation. It establishes a first candidate independent set from the complement of Hvala's cover and evaluates a dynamic minimum-degree Caro-Wei baseline. For every vertex in the cover---and explicitly including the graph's maximum degree vertex---a repair step removes it, reinstates its neighbors, and regrows a maximal independent set using an $O(n + m)$ conflict resolution and bucket-sort degree-scan phase, keeping the best of all these attempts. We prove that the output is always a maximal independent set and establish that the combination of the Caro-Wei baseline and explicit $v_{\max}$ repair mathematically guarantees an approximation ratio of $O(\sqrt{n})$ in $O(n^3)$ worst-case time. We offer robust theoretical proof and empirical evidence of the algorithm's effectiveness across 30,000 MILP-certified instances, achieving a worst-case approximation ratio of 4/3.