The Esperanza Algorithm for Maximum Independent Set

Introduction

Given an undirected graph $G=(V,E)$, an independent set is a subset $S \subseteq V$ in which no two vertices are joined by an edge. The maximum independent set (MIS) problem asks for such a set of largest possible cardinality; its size is the independence number $\alpha(G)$. A set $C \subseteq V$ is a vertex cover if every edge has an endpoint in $C$; $C$ is a vertex cover if and only if $V \setminus C$ is independent, so the minimum cover size is $\tau(G)=n-\alpha(G)$. We write $n=|V|$, $m=|E|$, $\Delta$ for the maximum degree, and $r(G)$ for the number of connected components of $G$ that contain an edge. The ratio of a returned independent set $S$ is $\rho=\alpha(G)/|S|$. MIS is on Karp’s list of NP-complete problems [1].

On general graphs, MIS cannot be approximated within $n^{1-\varepsilon}$ for any $\varepsilon> 0$ unless NP = ZPP [2], and the same threshold is NP-hard [3]. The best known polynomial-time ratios are $O(n/(\log n)^2)$ by subgraph exclusion [4] and $O(n(\log\log n)^2/(\log n)^3)$ [5]. On graphs of maximum degree $\Delta$, the minimum-degree greedy algorithm has ratio $(\Delta+2)/3$ [6], and the best known ratio, due to Halperin [7], is $O(\Delta\log\log\Delta/\log\Delta)$. Under the Unique Games Conjecture [8], Austrin, Khot and Safra proved that MIS on graphs of maximum degree $\Delta$ is hard to approximate within $O(\Delta/\log^2\Delta)$ [9], and Chan proved that $O(\Delta/\log^4\Delta)$ is NP-hard without any conjecture [10]. Khot and Regev proved, under UGC, that for every $\varepsilon,\delta> 0$ it is hard to distinguish graphs with an independent set of $(\frac{1}{2}-\varepsilon)n$ vertices from graphs with no independent set of more than $\delta n$ vertices; equivalently, Minimum Vertex Cover is hard to approximate within $2-\varepsilon$ for every $\varepsilon> 0$ [11]. In October 2026 the OpenAI Math Team released a manuscript with Lean artifacts reporting a proof of UGC in the NP-hardness form that the theorem of Khot and Regev requires [12]; at the time of writing it has not been peer reviewed. If it holds, both hardness results above hold unless P = NP.

This paper describes version 0.1.6 of Esperanza, which is implemented in Python [13]. The algorithm takes the best of a dynamic minimum-degree (Caro–Wei) greedy set [14, 15, 6] and the complement of the vertex cover returned by Salvador [16, 17], and improves it by three budgeted local searches: a repair-and-grow restart at every cover vertex and at a maximum-degree vertex, chained local restarts that realise $(k,k+1)$-improvements, and an iterated $(1,2)$-swap local search [18].

Contributions. The contributions of this paper are:

• The algorithm (§ 3, Algorithms 1–4) and the proof that it returns a maximal independent set (Theorem 4.5).

• A near-linear running time: for fixed work budgets the algorithm runs in $O((n+m)\alpha_A(n))$ expected time, with $\alpha_A$ the inverse Ackermann function (Theorem 7.2).

• Proved bounds (§ 5): the complementary vertex cover $V \setminus S$ is never larger than the Salvador cover, so $|V \setminus S| \le2\tau(G)-r(G)$ on every graph without self-loops (Theorem 5.1); $|S| \ge2\alpha(G)-n+r(G)$ (Corollary 5.2); and $|S| \ge\sum_v 1/(\deg v+1)$ with ratio at most $(\Delta+2)/3$ on graphs of maximum degree $\Delta$ (Theorem 5.3); and the ratio $2\sqrt{n}$ on every graph with $\Delta\le\sqrt{n}$ and on three further classes (Theorem 5.4).

• The conjecture that the ratio is at most $2\sqrt{n}$ on every graph (Conjecture 6.6), with the theorem that a proof would imply P = NP (Theorem 6.7).

• The conjecture that $|V \setminus S| \le2\tau(G)-|M|$ for the NetworkX minimum maximal matching $M$ (Conjecture 6.1), which is implied by the corresponding conjecture for Salvador, a per-instance certificate for it, and the conditional theorem that a proof would refute UGC unless P = NP, and would imply P = NP if the theorem reported in [12] holds (Theorem 6.5).

• Reproducible experiments (§ 8): 30 000 graphs with an optimum certified by an exact integer program, 40 YES-type instances of the Khot–Regev reduction with 640 to 2 560 vertices, and 31 bounded-degree graphs with $\Delta$ up to 128.

Section 3 describes the algorithm, Section 4 proves correctness, Section 5 the bounds, Section 6 states the conjecture and its consequences, and Section 7 the running time. Section 8 reports the experiments and Section 9 concludes.

Research Data

The algorithm is implemented in the Python package esperanza, available on the Python Package Index [13]. The version described in this paper is v0.1.6. Table 1 lists the code metadata.

Nr.	Code metadata description	Metadata
C1	Current code version	v0.1.6
C2	Permanent link to code/repository	https://github.com/frankvegadelgado/esperanza
C3	Permanent link to Reproducible Capsule	https://pypi.org/project/esperanza/
C4	Legal Code License	MIT License
C5	Code versioning system used	git
C6	Languages, tools, and services used	Python
C7	Compilation requirements and dependencies	Python $\ge3.12$, Salvador $\ge0.1.4$
C8	Experiment scripts (§ 8)	car/ directory of the repository

The Esperanza Algorithm

Algorithms 1–4 give the pseudo-code of Esperanza; they follow the published implementation (version 0.1.6 [13]). Throughout, $G$ denotes the working graph obtained in Algorithm 1 after removing self-loops and isolated vertices; its parameters $n$, $m$ and $\Delta$ are those of the working graph. For a set $S$ and a vertex $v$, the tightness of $v$ is $t_S(v)=|N(v)\cap S|$.

Algorithm 1 FindIndependentSet($G$; $B_R$, $B_L$, $B_I$, $\sigma$)

Require: Undirected graph $G=(V,E)$; work budgets $B_R$, $B_L$, $B_I$ (default 100 each); seed $\sigma$

Ensure: A maximal independent set of $G$

1. if $|V|=0$ then return $\emptyset$

2. end if

3. $G\leftarrow G.\mathrm{copy}()$; remove all self-loops from $G$

4. $I_{\mathrm{iso}}\leftarrow\{v\in V:\deg_G(v)=0\}$; remove $I_{\mathrm{iso}}$ from $G$

5. if $|V(G)|=0$ then return $I_{\mathrm{iso}}$

6. end if

7. $I_{\mathrm{CW}}\leftarrow\mathrm{PureCaroWeiBaseline}(G)$ ▷ Algorithm 2

8. $C\leftarrow\mathrm{Salvador}(G)$ ▷ [16, 17]; Lemma 4.3

9. $S\leftarrow I_{\mathrm{CW}}$ if $|I_{\mathrm{CW}}|>|V(G)\setminus C|$ else $V(G)\setminus C$

10. $v_{\max}\leftarrow$ a vertex of maximum degree in $G$

11. $I_R\leftarrow V(G)\setminus\mathrm{RefineCover}(G,C,v_{\max},B_R)$ ▷ restarts from $C\cup\{v_{\max}\}$

12. if $|I_R|>|S|$ then $S\leftarrow I_R$

13. end if

14. $I_L\leftarrow\mathrm{LocalRestartSearch}(G,S,B_L)$ ▷ Algorithm 4

15. if $|I_L|>|S|$ then $S\leftarrow I_L$

16. end if

17. $I_I\leftarrow V(G)\setminus\mathrm{ImproveVertexCover}(G,V(G)\setminus S,B_I,\sigma)$ ▷ (1, 2)-swaps [18]

18. if $|I_I|>|S|$ then $S\leftarrow I_I$

19. end if

20. $S\leftarrow\mathrm{MaximizeSolution}(G,S)$ ▷ Algorithm 3

21. return $S\cup I_{\mathrm{iso}}$

The calls to Salvador. Three routines of the package salvador (version $\geq0.1.4$) [17] are used. $\mathrm{Salvador}(G)$ in line 8 is salvador.algorithm.find_vertex_cover, the final cover of the seventeen-strategy ensemble of [16]. $\mathrm{RefineCover}(G,C,v_{\max},B)$ in line 11 is salvador.algorithm.refine_cover: for every $u\in C\cup\{v_{\max}\}$ it forms the vertex cover $(C\setminus\{u\})\cup N(u)$, that is, it moves $u$ into $V\setminus C$ and evicts the neighbours of $u$, grows the resulting independent set into a maximal one by $\mathrm{MaximizeSolution}$, and keeps the smallest resulting cover. When $C$ is a minimal cover, the routine evaluates each restart locally on the neighbours of the evicted vertices, which gives the same set as the global $\mathrm{MaximizeSolution}$ pass; every adjacency scan and the sorting of every local list are charged to a work counter, and the routine stops when the next restart would exceed $B(n+m)$. $\mathrm{ImproveVertexCover}(G,C',B,\sigma)$ in line 17 is salvador.local_search.improve_vertex_cover: it improves the independent set $V\setminus C'$ by the (1, 2)-swaps of Andrade, Resende and Werneck [18], which remove one solution vertex and insert two non-adjacent 1-tight neighbours of it, followed by an iterated local search that forces a random vertex into the set, re-inserts free vertices, runs (1, 2)-swaps around the change and undoes the step when the set shrinks. Its random choices use the fixed seed $\sigma$ (ILS_SEED = 20261031 in the package), and its work is charged to a counter with limit $B(n+m)$.

Local restarts. Algorithm 4 applies the restart of $\mathrm{RefineCover}$ to the incumbent $S$ instead of the $\mathrm{Salvador}$ cover. A move at $u\notin S$ forces $u$ into $S$, evicts the $k=t(u)$ vertices of $X=N(u)\cap S$, and refills the freed region with every vertex $w\in N(X)$ that has no neighbour left in $S$, in ascending order of degree. The move is committed when it inserts at least $k$ vertices besides $u$, a $(k,k+1)$-improvement, and undone otherwise; committed moves requeue the vertices whose tightness decreased, so improvements are chained.

Algorithm 2 PureCaroWeiBaseline($G$): dynamic minimum-degree greedy

Require: Undirected graph $G = (V, E)$

Ensure: A maximal independent set $I$ with $|I| \ge\sum_{v} 1/(\operatorname{deg}_G(v) + 1)$

1: $\operatorname{deg}[v] \leftarrow\operatorname{deg}_G(v)$ for every $v$; place every $v$ into bucket $B[\operatorname{deg}[v]]$; $\operatorname{ptr} \leftarrow0$ 2: $\operatorname{removed} \leftarrow\varnothing$; $I \leftarrow\varnothing$ 3: while some vertex is not removed do 4: &nbsp;&nbsp;&nbsp;&nbsp;advance $\operatorname{ptr}$ to the first bucket whose front is not removed, discarding removed fronts 5: &nbsp;&nbsp;&nbsp;&nbsp;$v \leftarrow$ pop front of $B[\operatorname{ptr}]$; $I \leftarrow I \cup\{v\}$; mark $v$ removed 6: &nbsp;&nbsp;&nbsp;&nbsp;for each neighbour $u$ of $v$ that is not removed do 7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mark $u$ removed 8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for each neighbour $w \ne v$ of $u$ that is not removed do 9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\operatorname{deg}[w] \leftarrow\operatorname{deg}[w] - 1$; append $w$ to $B[\operatorname{deg}[w]]$ 10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $\operatorname{deg}[w] < \operatorname{ptr}$ then $\operatorname{ptr} \leftarrow\operatorname{deg}[w]$ 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if 12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end for 13: &nbsp;&nbsp;&nbsp;&nbsp;end for 14: end while 15: return $I$

Algorithm 3 MaximizeSolution($G$, $S$): repair and grow in $O(n + m)$

Require: Undirected graph $G = (V, E)$; candidate set $S \subseteq V$ (may contain conflicts)

Ensure: A maximal independent set of $G$

1: $I \leftarrow S$; $\operatorname{conflicts}[u] \leftarrow|N(u) \cap I|$ for $u \in I$ 2: for each edge $\{u, v\} \in E$ do                                      ▹ Phase 1: conflict resolution 3: &nbsp;&nbsp;&nbsp;&nbsp;if $u \in I$ and $v \in I$ then 4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\ell\leftarrow u$ if $\operatorname{conflicts}[u] \ge\operatorname{conflicts}[v]$ else $v$ 5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$I \leftarrow I \setminus\{\ell\}$; decrement $\operatorname{conflicts}[w]$ for every $w \in N(\ell) \cap I$ 6: &nbsp;&nbsp;&nbsp;&nbsp;end if 7: end for 8: place every $u \notin I$ into the bucket $B[\operatorname{deg}_G(u)]$                       ▹ Phase 2: growth by counting sort 9: for $d = 0, \ldots, \Delta$ do 10: &nbsp;&nbsp;&nbsp;&nbsp;for each $u \in B[d]$ do 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $N(u) \cap I = \varnothing$ then $I \leftarrow I \cup\{u\}$ 12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if 13: &nbsp;&nbsp;&nbsp;&nbsp;end for 14: end for 15: return $I$

Algorithm 4 LocalRestartSearch($G$, $S$, $B$): budgeted local restarts
Require: Graph $G$ without self-loops; independent set $S$; budget $B$
Ensure: An independent set $S'$ with $|S'| \ge |S|$
1: maintain $t(v)=|N(v)\cap S|$ for every $v$; work $\leftarrow$ cost of the initialisation; limit $\leftarrow$ work $+B(n+m)+1$
2: $Q \leftarrow$ the vertices outside $S$, sorted by $(t(v),\deg v)$ with two counting sorts
3: while $Q\ne\varnothing$ and work $\le$ limit do
4: \phantom{while }u \leftarrow Q.\mathrm{PopFront}(); work $\leftarrow$ work $+1$
5: \phantom{while }if $u\in S$ then continue
6: \phantom{while }end if
7: \phantom{while }if $t(u)=0$ then insert $u$ into $S$; continue
8: \phantom{while }end if
9: \phantom{while }$X\leftarrow N(u)\cap S$; $T\leftarrow\sum_{x\in X}\deg x$; work $\leftarrow$ work $+\deg u$
10: \phantom{while }if work $+3(T+\deg u+|X|+1)+T\log_2(T+1)>\mathrm{limit}$ then continue
11: \phantom{while }end if
12: \phantom{while }remove every $x\in X$ from $S$; insert $u$ into $S$ \hfill $\triangleright$ logged
13: \phantom{while }$R\leftarrow\{w\in N(X):w\notin S,\ t(w)=0\}$, sorted by $(\deg w,w)$
14: \phantom{while }for each $w\in R$ do
15: \phantom{while }\phantom{while }if $w\notin S$ and $t(w)=0$ then insert $w$ into $S$ \hfill $\triangleright$ logged
16: \phantom{while }\phantom{while }end if
17: \phantom{while }end for
18: \phantom{while }if $S$ grew then append to $Q$ every $w\in N(X)\setminus S$ not in $Q$ \hfill $\triangleright$ commit
19: \phantom{while }else undo the logged operations
20: \phantom{while }end if
21: end while
22: return $S$

Correctness of the Algorithm

Proof. During Phase 1 the set only shrinks. If an edge had both endpoints in the set at the end of Phase 1, both endpoints would have been present when that edge was scanned, and one of them would have been discarded; so the set is independent after Phase 1. A vertex of $S'$ without neighbours in $S'$ never lies on a scanned conflicting edge, so it is never discarded. Phase 2 adds a vertex only if it has no neighbour in the current set, so independence is preserved. Every vertex outside the set after Phase 1 is placed in a bucket and examined; if it is rejected, it has a neighbour in the set at that moment, and that neighbour is never removed. Hence the output is maximal.

Proof. A chosen vertex is never adjacent to a previously chosen one, because all neighbours of a chosen vertex are removed at once; every vertex is either chosen or removed as a neighbour of a chosen vertex, so $I$ is maximal. Degrees only decrease, and every vertex is appended to the bucket of its current degree whenever that degree changes, with the pointer moved back when a degree drops below it. Hence a vertex popped from bucket ptr that is not removed has current degree at most ptr, and every bucket below ptr contains only removed vertices; so the chosen vertex has minimum current degree. Let $v$ be chosen when its current degree is $d$, and let $N[v]$ be its closed neighbourhood in the current graph. Every $u\in N[v]$ has current degree at least $d$ and original degree at least its current degree, so $\sum_{u\in N[v]}\frac{1}{\deg_G(u)+1}\le(d+1)\frac{1}{d+1}=1$. The closed neighbourhoods of the chosen vertices partition $V$, so $\sum_{v\in V}\frac{1}{\deg_G(v)+1}\le|I|$, and $\deg_G(v)\le\Delta$ gives the second inequality.

Proof. (i) is the bound $2\tau-r$ and the running time proved for Salvador 0.1.4 in [16]. For (ii), RefineCover returns either its input or a cover of the form $V \setminus I$ with $I$ independent and strictly larger than $V \setminus C$; ImproveVertexCover returns the complement of an independent set that is at least as large as the complement of its input, because worse steps are undone. The running times are those of the strategies $c_{17}$ and $c_{14}$ of [16], whose work counters stop after $B(n+m)$ units plus the cost of one step, which is $O(n+m)$.

Proof. The tightness counters are updated on every insertion and removal, so $t(v)=|N(v)\cap S|$ holds at all times. A vertex is inserted only when its tightness is 0: a free vertex directly, the vertex $u$ after all of $N(u)\cap S$ has been removed, and a refill vertex $w$ after the check $t(w)=0$. Hence $S$ stays independent. A free insertion increases $|S|$. A move is kept only if $1+(\text{number of refill insertions})>|X|$, that is, if $|S|$ increases; otherwise the log is undone in reverse order, which restores $S$ and all counters. So $|S|$ never decreases.

Proof. $I_{\mathrm{CW}}$ is independent by Lemma 4.2. $V(G)\setminus C$, $I_R$ and $I_I$ are complements of vertex covers by Lemma 4.3, hence independent, and $I_L$ is independent by Lemma 4.4. So the incumbent $S$ is independent before the last call, and MaximizeSolution$(G,S)$ returns a maximal independent set of the working graph by Lemma 4.1. Isolated vertices have no neighbours, so $S\cup I_{\mathrm{iso}}$ is independent in the input graph; it is maximal, because a vertex outside it is a non-isolated vertex of the working graph and has a neighbour in $S$.

Proved Bounds

Proof. $V\setminus S$ is a vertex cover because $S$ is independent (Theorem 4.5). The incumbent starts with at least $|V(G)\setminus C|$ vertices and is only replaced by larger sets; the final MaximizeSolution call keeps the incumbent, which is independent, by Lemma 4.1. Hence $|S|\ge|V(G)\setminus C|+|I_{\mathrm{isol}}|$, and $|V\setminus S|\le|C|$. Isolated vertices change neither $\tau$ nor $r$, so Lemma 4.3(i) gives $|C|\le2\tau(G)-r(G)$.

The package exposes this cover as esperanza.algorithm.find_vertex_cover, which also adds every vertex with a self-loop.

Proof. By Theorem 5.1, $|S|\ge n-2\tau(G)+r(G)=n-2(n-\alpha(G))+r(G)$. For $\alpha=\beta n$ with $\beta>\frac{1}{2}$ this gives $|S|\ge(2\beta-1)n$.

Proof. The incumbent starts with at least $|I_{\mathrm{CW}}|$ vertices on the working graph and never shrinks (proof of Theorem 5.1), and isolated vertices are added to both $S$ and every maximum independent set. $I_{\mathrm{CW}}$ is produced by the minimum-degree greedy rule (Lemma 4.2), which has ratio at most $(\Delta+ 2)/3$ on graphs of maximum degree $\Delta$ [6], and satisfies the Caro–Wei bound by Lemma 4.2.

Proof. By the proofs of Theorems 5.1 and 5.3, $|S| \ge|V \setminus C|$ and $|S| \ge|I_{\mathrm{CW}}|$. (a) $S$ is non-empty, so $\alpha/|S| \le\alpha\le2\sqrt{n}$. (b) $|C| \le2\tau= 2(n-\alpha)$ by Lemma 4.3(i), so $|S| \ge n-|C| \ge2\alpha-n \ge\alpha/\sqrt{n}$ and $\alpha/|S| \le\sqrt{n}$. (c) $I^* \setminus C \subseteq V \setminus C$, so $|S| \ge|I^* \setminus C| \ge\alpha/\sqrt{n}$ and $\alpha/|S| \le\sqrt{n}$. (d) By Lemma 4.2 and $\alpha\le n$,

where $\frac{n}{\sqrt{n}+1} \ge\frac{\sqrt{n}}{2}$ is equivalent to $n \ge\sqrt{n}$. Hence $\alpha/|S| \le2\sqrt{n}$.

The four conditions do not cover every graph. A graph satisfies none of them exactly when $\Delta> \sqrt{n}$, $2\sqrt{n} < \alpha$, $2\alpha-n < \alpha/\sqrt{n}$ and $|I^* \setminus C| < \alpha/\sqrt{n}$ for every maximum independent set $I^*$. In that case every maximal independent set has at least $n/(\Delta+1)$ vertices, because each of its vertices dominates at most $\Delta+1$ vertices, but $n/(\Delta+1) < \alpha/(2\sqrt{n})$, and this does not give $|S| \ge\alpha/(2\sqrt{n})$. The ratio $2\sqrt{n}$ on all graphs is therefore stated as Conjecture 6.6 in § 6. On general graphs, by [2, 3], a polynomial-time ratio of $n^{1-\varepsilon}$ for some $\varepsilon> 0$ would imply P = NP.

The barrier $\Delta/\log_2^2 \Delta$. Austrin, Khot and Safra proved that, assuming the Unique Games Conjecture, Maximum Independent Set on graphs of maximum degree $\Delta$ is hard to approximate within a factor $O(\Delta/\log_2^2 \Delta)$ for all sufficiently large $\Delta$ [9]. Without any conjecture, Chan proved that the factor $O(\Delta/\log^4 \Delta)$ is NP-hard [10], and the best known polynomial-time ratio is $O(\Delta\log\log\Delta/\log\Delta)$ [7]. Consequently, a polynomial-time algorithm whose ratio on graphs of maximum degree $\Delta$ is $o(\Delta/\log_2^2 \Delta)$ as $\Delta\to\infty$ would refute the Unique Games Conjecture unless P = NP. The ratio $(\Delta+2)/3$ proved in Theorem 5.3 is linear in $\Delta$, so it lies above this threshold for large $\Delta$ and is consistent with both hardness results. § 8.3 reports the measured ratios of Esperanza together with the value $\Delta/\log_2^2 \Delta$ for each instance; since the threshold is asymptotic and its constant is not explicit, finite instances do not decide whether the ratio of Esperanza grows more slowly than $\Delta/\log_2^2 \Delta$.

The Conjectured Bounds and Their Consequences

Let $M$ be the maximal matching returned by NetworkX’s min_maximal_matching [19] on the working graph; it is the matching of the strategy $c_2$ of Salvador [16]. Every vertex cover contains an endpoint of each of the $|M|$ disjoint edges of $M$, and the $2|M|$ matched vertices form a vertex cover, so $|M| \le\tau(G) \le2|M|$.

Proof. $|V \setminus S| \le|C|$ by Theorem 5.1. The second statement follows from $|M| \ge\tau(G)/2$.

Proof. $2L - |M| \le2\tau- |M| \le2U - |M|$, and $\frac{3}{2}L \le\frac{3}{2}\tau$.

Proof. $\tau(G) = n - \alpha(G) \ge(1 - \delta)n$ and $|M| \le n/2$, so $|C'| - \tau\le n - \tau\le\delta n \le(\frac{1}{2} - \delta)n \le\tau- |M|$.

Proof. Algorithm 1 runs in polynomial time (Theorem 7.2), and the function $G \mapsto V \setminus S$ returns a vertex cover. A proof of Conjecture 6.1 makes it a $\frac{3}{2}$-approximation (Proposition 6.2), a ratio of the form $2 - \varepsilon_0$ with $\varepsilon_0 = \frac{1}{2}$, so under the assumption it solves an NP-hard problem in polynomial time. The theorem of Khot and Regev [11] derives the assumption from UGC.

Theorem 6.5 is a conditional implication, not a proof of P = NP. The theorem of [12] had not been peer reviewed at the time of writing; we cite it as reported and have not checked the formalization. By Proposition 6.4, a counterexample to Conjecture 6.1 with $\alpha\le n/4$ does not exist, so a counterexample has an independent set of more than a quarter of the vertices.

By Theorem 5.4, Conjecture 6.6 holds on every graph that satisfies one of the conditions (a)–(d), in particular on every graph with $\Delta\le\sqrt{n}$; a counterexample has $\Delta> \sqrt{n}$ and satisfies none of (a)–(c).

Proof. Algorithm 1 runs in polynomial time (Theorem 7.2). For $n \ge16$, $2\sqrt{n} \le n^{3/4}$, so Conjecture 6.6 would give a polynomial-time approximation of Maximum Independent Set within $n^{1-\varepsilon}$ with $\varepsilon= \frac{1}{4}$, which is NP-hard [3].

Runtime Analysis

Hash-table operations on vertex sets are counted as $O(1)$ expected time, as in the implementation.

Proof. The initialisation, the counters and the two counting sorts take $O(n + m + \Delta) = O(n + m)$ time. Every operation of the main loop is charged to the counter work: each pop costs 1, the computation of $X$ costs $\deg u$, every insertion or removal of a vertex $v$ costs $\deg v + 1$, the scan of $N(X)$ costs $\sum_{x\in X}\deg x$, the sort of $k$ refill candidates costs $k\log_2 k$, and the requeueing costs $\sum_{x\in X}\deg x$. The loop runs only while work $\le$ limit $= O(B(n + m) + n + m)$, and a move is started only if work plus the bound $3(T + \deg u + |X| + 1) + T\log_2(T + 1)$ is at most limit. The bound covers every charge of the move except the insertions of the refill candidates and their updates, which cost at most $2\sum_w(\deg w + 1) \le2(2m + n)$ over distinct vertices $w$; such a move ends the loop as soon as work exceeds limit. Hence the total work is $O(B(n + m) + n + m)$.

Proof. Copying the graph and removing self-loops and isolated vertices take $O(n+m)$ time. Algorithm 2 takes $O(n+m)$ time: every vertex is removed once, every degree decrement costs $O(1)$ and appends one bucket entry, and the pointer moves forward at most $\Delta$ times plus once for every backward move, each of which follows a decrement. Salvador takes $O((n+m)\alpha_A(n))$ time, and RefineCover and ImproveVertexCover take $O(B(n+m)+n+m)$ time each (Lemma 4.3). Building the adjacency lists, Algorithm 4 (Lemma 7.1), Algorithm 3, the set differences and the comparisons take $O(B(n+m)+n+m)$ time.

With the default budgets $B_R=B_L=B_I=100$, the bound of Theorem 7.2 is $O((n+m)\alpha_A(n))$. Passing restart_budget=None removes the cap of RefineCover, whose running time is then $O(|C|(n+m))$.

Experiments

All experiments use Esperanza 0.1.6 and Salvador 0.1.4, and the three scripts of the folder car/ of the repository: experiment.py (§ 8.1), ugc_candidate.py (§ 8.2) and bounded_degree.py (§ 8.3). The scripts import the repository’s own esperanza/. Exact optima and bounds are computed with scipy.optimize.milp [20], which calls the HiGHS solver [21]. The environment is Windows 11, Python 3.12.3 and NetworkX 3.6.1 [19]; wall-clock times are machine dependent.

Certified suite of 30000 graphs

Instance generation. A single master generator random.Random(42) is consumed in the order of Table 2. Each random graph receives its own seed, drawn as randrange(2^{31}) from the master generator. The amplified family is built after the first six. Its bases are the connected gnp and regular instances with $n \le12$, ranked by their ratio $\rho$ with a stable sort, of which the first 25 are kept; since $\rho=1$ on all of them, these are the first 25 such instances in generation order. Each amplified instance draws a base uniformly. With probability $1/2$ it is a disjoint union of $c \sim U\{2,\ldots,8\}$ copies of the base, and otherwise an independent blow-up with cluster size $t \sim U\{2,\ldots,6\}$, in which each vertex becomes $t$ pairwise non-adjacent copies and each edge a complete bipartite join between the corresponding clusters.

Family	Count	Generator	Parameters	$n$	$m$
gnp	15000	gnp_random_graph($n$, $p$)	$n \sim U\{6,\ldots,16\}$, $p \sim U(0.15,0.85)$	6–16	0–109
bipartite_gnp	6000	bipartite_random_graph($a,b,p$)	$a,b \sim U\{3,\ldots,14\}$, $p \sim U(0.10,0.50)$	6–28	0–104
regular	3000	random_regular_graph($d,n$)	$d \sim U\{3,\ldots,5\}$, $n \in\{\max(d+1,8),\ldots,16\}$, $nd$ even	8–16	12–40
star	2000	star_graph($k$)	$k \sim U\{3,\ldots,80\}$	4–81	3–80
complete	1000	complete_graph($n$)	$n \sim U\{3,\ldots,30\}$	3–30	3–435
complete_bipartite	1000	complete_bipartite_graph($a,b$)	$a \sim U\{2,\ldots,12\}$, $b \sim U\{a,\ldots,20\}$	4–32	4–240
amplified	2000	disjoint union or blow-up	see text	12–96	16–1368

Exact optimum. For each instance we solve

with the default options of scipy.optimize.milp (no time limit; HiGHS relative gap tolerance $10^{-4}$), accept a solve only when HiGHS reports an optimal status, and round the objective to the nearest integer; since $\alpha(G)\le96$, the tolerance is below one vertex, so the rounded value is $\alpha(G)$. Every returned set is verified to be independent. The reported ratio is $\rho=\alpha(G)/|S|$.

Results. Esperanza 0.1.6 returns a maximum independent set on all 30 000 instances; the worst and the mean ratio are 1.000000 in every family (Table 3), and the returned sets have 269 247 vertices in total. The complete run, including the integer programs, took 747.9 s.

Family	Count	Worst	Mean
gnp	15000	1.000	1.000
bipartite_gnp	6000	1.000	1.000
regular	3000	1.000	1.000
star	2000	1.000	1.000
complete	1000	1.000	1.000
complete_bipartite	1000	1.000	1.000
amplified	2000	1.000	1.000
All	30000	1.000	1.000

YES-type instances of the Khot–Regev reduction

The instances are those of Part D of the Salvador experiments [16], with the same generator, seed (20261009) and instance names. A Unique Games instance with labels $[k]$ is generated on a random $d$-regular graph with $N$ vertices and a planted labelling $L$, each edge carrying a permutation $\pi_{vw}$ with $\pi_{vw}(L(w)) = L(v)$ (random, or a shift modulo $k$ in the linear variant), and a fraction $\eta$ of the edges receive a random constraint. Every vertex $v$ becomes a block of $s$ subsets $x \subseteq[k]$ drawn from the $p$-biased measure, and $(v,x)$ and $(w,y)$ are joined when $x$ and $\pi_{vw}(y)$ are disjoint [11].

The dictator set $\{(v,x) : L(v) \in x\}$, made independent greedily on violated constraints, gives the planted cover, an upper bound on $\tau$. The base family has $k = 4$, $p = 0.45$, $\eta= 0$, $d = 4$, $s = 16$, and nine more change one parameter. With $N \in\{40, 80\}$ and two instances per family and size, this gives 40 instances with 640 to 2 560 vertices.

For every instance, $L$ is the larger of the linear relaxation and the dual bound of an integer program (HiGHS, 90 s), and $U$ is the smaller of the planted cover, the integer-program value and the two covers computed; the integer program proved $\tau$ on 26 instances. Each instance is classified by Proposition 6.3 as certified ($|C| \le2L - |M|$), violated ($|C| > 2U - |M|$) or open, for $C = V \setminus S$ (E) and for the Salvador cover (S). Table 4 reports the counts.

Family	Inst.	E cert.	E open	E viol.	S cert.	S open	S viol.	E<S	Opt.	$\frac{3}{2}$	max $|C|/L$	min $|S|/n$
Base family ($k = 4$, $p = 0.45$, $\eta= 0$)	4	4	0	0	4	0	0	0	2	4	1.0487	0.4445
Label size $k = 3$	4	4	0	0	4	0	0	0	3	4	1.0232	0.4469
Label size $k = 6$	4	4	0	0	4	0	0	0	4	4	1.0000	0.5055
Bias $p = 0.35$	4	3	1	0	3	1	0	1	1	4	1.1513	0.3812
Bias $p = 0.49$	4	4	0	0	4	0	0	0	4	4	1.0000	0.5070
Noise $\eta= 0.02$	4	4	0	0	4	0	0	0	1	4	1.0468	0.4406
Noise $\eta= 0.1$	4	4	0	0	4	0	0	0	0	4	1.0239	0.4469
Constraint degree $d = 8$	4	4	0	0	4	0	0	0	3	4	1.0067	0.4164
Samples per block $s = 32$	4	3	1	0	3	1	0	0	0	4	1.1483	0.4191
Linear UG, Max-2-Lin($\mathbb{Z}_k$)	4	4	0	0	4	0	0	1	1	4	1.0148	0.4656
All	40	38	2	0	38	2	0	2	19	40	1.1513	0.3812

The inequality $|C| \le2\tau- |M|$ is certified on 38 instances and violated on none, for both covers. The two open instances have $\tau$ unknown: on kr_p0.35_N80_r0 ($n = 1\,280$), $|C| = 776$, $|M| = 574$ and $L = 674$, so $2L - |M| = 774$; on kr_s32_N80_r0 ($n = 2\,560$), $|C| = 1\,487$, $|M| = 1\,134$ and $L = 1\,295$, so $2L - |M| = 1\,456$. On both, the two covers have the same size. Esperanza is strictly smaller than Salvador on two instances (683 against 707 on kr_linear_N80_r0, and 763 against 766 on kr_p0.35_N80_r1). Where $\tau$ is known, the cover is optimal on 19 of 26 instances, with mean ratio 1.0024 and maximum 1.0232 (705 against 689 on kr_s32_N40_r0, planted cover 690). The cover is no larger than the planted one on 34 instances and strictly smaller on 28. Every instance passes the $\frac{3}{2}$ certificate, and the largest certified ratio is $|C|/L = 1.1513$. In the independent-set form of the reduction, the returned set contains at least 0.3812 $n$ vertices on every instance. Esperanza took at most 5.72 s per instance (mean 2.01 s), and the whole run 2 058.9 s, mostly in the integer programs.

Bounded-degree graphs

The script bounded_degree.py measures the ratio on graphs of bounded degree. For every instance it computes $S$ and the range $\alpha_{\mathrm{low}} \le\alpha(G) \le\alpha_{\mathrm{up}}$, where $\alpha_{\mathrm{low}}$ is the largest of $|S|$, the planted independent set, the two baselines below and the integer-program value, and $\alpha_{\mathrm{up}}$ is the smaller of $n$ minus the linear relaxation of vertex cover and the integer-program dual bound (HiGHS, 60 s). It reports $\alpha_{\mathrm{up}/|S|}$, a certified upper bound on the ratio, the same bound for the Caro–Wei baseline $I_{\mathrm{CW}}$ and for the complement of the Salvador cover, and the normalised value $(\alpha_{\mathrm{up}}/|S|)/(\Delta/\log_2^2 \Delta)$, with $\Delta$ the maximum degree of the instance. There are three families: random $\Delta$-regular graphs; graphs of maximum degree at most $\Delta$ with a planted independent set of $\beta n$ vertices, $\beta\in\{0.35, 0.45\}$, in which every planted vertex has $\Delta$ random neighbours outside the planted set and the remaining stubs outside it are paired at random; and Khot–Regev YES graphs with $k = 4$, $p = 0.45$, $\eta= 0$, $d \in\{3, 4\}$ and $s \in\{4, 8, 16\}$ samples per block. The run uses $n = 256$ for the first two families, $N \in\{16, 64\}$ for the third (64 to 1 024 vertices) and one instance per setting, 31 instances in total; the integer program proved $\alpha$ on 17 of them (Table 5).

Family	$\Delta$ set	$\Delta$	Inst.	Exact	Opt.	max up	mean up	max low	CW	Salv.	$\Delta/\log_2^2 \Delta$	norm.
kr	12	12	2	2	2	1.0000	1.0000	1.0000	1.0134	1.0000	0.9337	1.0710
kr	24	24	2	2	2	1.0000	1.0000	1.0000	1.0714	1.0000	1.1417	0.8759
kr	32	32	2	2	2	1.0000	1.0000	1.0000	1.0246	1.0000	1.2800	0.7812
kr	64	64	2	2	1	1.0086	1.0043	1.0086	1.0636	1.0086	1.7778	0.5673
planted	4	4	2	1	1	1.0577	1.0288	1.0000	1.1500	1.0577	1.0000	1.0577
planted	8	8	2	1	1	1.0769	1.0385	1.0000	1.1136	1.0769	0.8889	1.2115
planted	16	16	2	2	2	1.0000	1.0000	1.0000	1.6667	1.0000	1.0000	1.0000
planted	32	32	2	2	2	1.0000	1.0000	1.0000	2.3077	1.0000	1.2800	0.7812
planted	64	62	2	2	2	1.0000	1.0000	1.0000	1.0000	1.0000	1.7488	0.5815
regular	3	3	1	1	0	1.0088	1.0088	1.0088	1.0270	1.0088	1.1942	0.8448
regular	4	4	1	0	0	1.0476	1.0476	1.0000	1.1224	1.0476	1.0000	1.0476
regular	5	5	1	0	0	1.0947	1.0947	1.0000	1.1556	1.0947	0.9274	1.1804
regular	6	6	1	0	0	1.1705	1.1705	1.0000	1.1839	1.1705	0.8979	1.3035
regular	8	8	1	0	0	1.2436	1.2436	1.0000	1.3288	1.2436	0.8889	1.3990
regular	12	12	1	0	0	1.4194	1.4194	1.0000	1.4915	1.4194	0.9337	1.5201
regular	16	16	1	0	0	1.5283	1.5283	1.0000	1.5882	1.5283	1.0000	1.5283
regular	24	24	1	0	0	1.6429	1.6429	1.0000	1.7692	1.6429	1.1417	1.4390
regular	32	32	1	0	0	1.8788	1.8788	1.0000	2.0667	1.8788	1.2800	1.4678
regular	48	48	1	0	0	2.0800	2.0800	1.0000	2.3636	2.0800	1.5389	1.3516
regular	64	64	1	0	0	2.2500	2.2500	1.0000	2.5000	2.2500	1.7778	1.2656
regular	96	96	1	0	0	2.4286	2.4286	1.0000	2.8333	2.4286	2.2139	1.0969
regular	128	128	1	0	0	2.4545	2.4545	1.0000	3.3750	2.4545	2.6122	0.9396

On the kr and planted families, $\alpha$ is proved on 16 of 18 instances and $S$ is optimal on 15 of them; the largest certified ratio is 1.0769. On the regular family, $\alpha$ is proved only for $\Delta= 3$ ($|S| = 113$, $\alpha= 114$), and for $\Delta\ge4$ the bound $\alpha_{\mathrm{up}}$ is the dual bound of the integer program at the time limit; for $\Delta= 128$, $|S| = 11$ and $\alpha_{\mathrm{up}} = 27$. On these instances $\alpha_{\mathrm{low}} = |S|$, so the ratio is only known to lie between 1 and the reported upper bound. On all 31 instances, the set $S$ has the same size as the complement of the Salvador cover. Esperanza took at most 1.48 s per instance, and the whole run 908.8 s.

Conclusion

Esperanza 0.1.6 returns a maximal independent set (Theorem 4.5) in $O((n + m)\alpha_A(n))$ expected time for fixed work budgets (Theorem 7.2). Its complementary vertex cover has at most $2\tau- r$ vertices (Theorem 5.1), and on graphs of maximum degree $\Delta$ its ratio is at most $(\Delta+ 2)/3$ (Theorem 5.3), above the UGC-hardness threshold $O(\Delta/\log_2^2 \Delta)$ of [9]; its ratio is at most $2\sqrt{n}$ on every graph with $\Delta\le\sqrt{n}$ and on the further classes of Theorem 5.4. On 30 000 graphs with a certified optimum it is optimal on every instance. On 40 Khot–Regev YES instances with 640 to 2 560 vertices, the inequality $|V \setminus S| \le2\tau- |M|$ is certified on 38 and open on 2, and on 31 bounded-degree graphs the certified upper bound on the ratio is at most 1.0769 on the families with a planted independent set and at most 2.4545 on random regular graphs of degree up to 128.

We do not claim that Esperanza has ratio $O(\sqrt{n})$ on every graph; this is Conjecture 6.6, and a proof would imply P = NP (Theorem 6.7). Nor do we claim that Esperanza is a $\frac{3}{2}$-approximation for Minimum Vertex Cover. The bound $|V \setminus S| \leq2\tau- |M|$ is a conjecture (Conjecture 6.1); the experiments concern graphs of at most 2 560 vertices; and a proof would refute UGC unless P = NP, and would imply P = NP if the theorem reported in [12] holds (Theorem 6.5). What is guaranteed on a given graph is the per-instance certificate of Proposition 6.3. The implementation is freely available as the esperanza package on PyPI [13].

Acknowledgements

The author would like to thank Iris, Marilin, Sonia, Yoselin, and Arelis for their support.

Statements and Declarations

Declaration of interests

The author declares no competing interests.

Funding sources

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Declaration of generative AI in scientific writing

The author designed the strategies of Esperanza, and used Claude Opus 5.5 to implement them by vibe coding and to improve the readability of this manuscript. After using this tool, the author reviewed and edited the code and the content as needed and takes full responsibility for the content of the publication.

Data availability

Code and data: https://github.com/frankvegadelgado/esperanza (release v0.1.6); the experiments of § 8 are reproduced by running the scripts of car/.