%% \documentclass[preprint,review,12pt]{elsarticle}
%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout.
\documentclass[final,3p,times]{elsarticle}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true,allcolors=blue}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{tabularx}
\usepackage{booktabs}
\usepackage{siunitx}
\usepackage{array}
\usepackage{float}
\usepackage{longtable}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\makeatletter
\providecommand{\theHALG@line}{}
\renewcommand{\theHALG@line}{\thealgorithm.\arabic{ALG@line}}
\makeatother

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}

\journal{Hexagon}

\begin{document}

\begin{frontmatter}

\title{The Esperanza Algorithm for Maximum Independent Set}

\author{Frank Vega}

\address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA}

\ead{vega.frank@gmail.com}

\begin{abstract}
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.
\end{abstract}

\begin{keyword}
Maximum Independent Set \sep Approximation Algorithm \sep Vertex Cover \sep Local Search \sep Bounded-degree Graphs \sep Linear Time \sep Unique Games Conjecture \sep P versus NP
\MSC[2020] 05C69 \sep 68Q25 \sep 68W25 \sep 90C27
\end{keyword}

\end{frontmatter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Given an undirected graph $G = (V, E)$, an \emph{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 \emph{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~\cite{karp1972reducibility}.

On general graphs, MIS cannot be approximated within $n^{1-\varepsilon}$ for any $\varepsilon>0$ unless $\mathrm{NP}=\mathrm{ZPP}$~\cite{hastad1999clique}, and the same threshold is NP-hard~\cite{zuckerman2007linear}. The best known polynomial-time ratios are $O(n/(\log n)^2)$ by subgraph exclusion~\cite{boppana1992approximating} and $O(n(\log\log n)^2/(\log n)^3)$~\cite{feige2004approximating}. On graphs of maximum degree $\Delta$, the minimum-degree greedy algorithm has ratio $(\Delta+2)/3$~\cite{halldorsson1994greedy}, and the best known ratio, due to Halperin~\cite{halperin2002improved}, is $O(\Delta\log\log\Delta/\log\Delta)$. Under the Unique Games Conjecture (UGC)~\cite{khot2002unique}, Austrin, Khot and Safra proved that MIS on graphs of maximum degree $\Delta$ is hard to approximate within $O(\Delta/\log^2\Delta)$~\cite{austrin2011inapproximability}, and Chan proved that $O(\Delta/\log^4\Delta)$ is NP-hard without any conjecture~\cite{chan2016approximation}. Khot and Regev proved, under UGC, that for every $\varepsilon,\delta>0$ it is hard to distinguish graphs with an independent set of $(\frac12-\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$~\cite{khot2008vertex}. 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~\cite{openai2026ugc}; at the time of writing it has not been peer reviewed. If it holds, both hardness results above hold unless $\mathrm{P}=\mathrm{NP}$.

This paper describes version 0.1.6 of \textsc{Esperanza}, which is implemented in Python~\cite{Vega26}. The algorithm takes the best of a dynamic minimum-degree (Caro--Wei) greedy set~\cite{caro1979new,wei1981lower,halldorsson1994greedy} and the complement of the vertex cover returned by \textsc{Salvador}~\cite{Vega26SalvadorPaper,Vega26Salvador}, 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~\cite{andrade2012fast}.

\paragraph{Contributions} The contributions of this paper are:
\begin{itemize}
\item The algorithm (Section~\ref{sec:algorithm}, Algorithms~\ref{alg:main}--\ref{alg:lrs}) and the proof that it returns a maximal independent set (Theorem~\ref{thm:correctness}).
\item A near-linear running time: for fixed work budgets the algorithm runs in $O((n+m)\,\alpha_{\mathrm A}(n))$ expected time, with $\alpha_{\mathrm A}$ the inverse Ackermann function (Theorem~\ref{thm:runtime}).
\item Proved bounds (Section~\ref{sec:ratio}): the complementary vertex cover $V\setminus S$ is never larger than the \textsc{Salvador} cover, so $|V\setminus S|\le2\tau(G)-r(G)$ on every graph without self-loops (Theorem~\ref{thm:cover}); $|S|\ge2\alpha(G)-n+r(G)$ (Corollary~\ref{cor:dense}); and $|S|\ge\sum_v1/(\deg v+1)$ with ratio at most $(\Delta+2)/3$ on graphs of maximum degree $\Delta$ (Theorem~\ref{thm:degree}); and the ratio $2\sqrt n$ on every graph with $\Delta\le\sqrt n$ and on three further classes (Theorem~\ref{thm:sqrt}).
\item The conjecture that the ratio is at most $2\sqrt n$ on every graph (Conjecture~\ref{conj:sqrt}), with the theorem that a proof would imply $\mathrm{P}=\mathrm{NP}$ (Theorem~\ref{thm:sqrtpnp}).
\item The conjecture that $|V\setminus S|\le2\tau(G)-|M|$ for the NetworkX minimum maximal matching $M$ (Conjecture~\ref{conj:esperanza}), which is implied by the corresponding conjecture for \textsc{Salvador}, a per-instance certificate for it, and the conditional theorem that a proof would refute UGC unless $\mathrm{P}=\mathrm{NP}$, and would imply $\mathrm{P}=\mathrm{NP}$ if the theorem reported in~\cite{openai2026ugc} holds (Theorem~\ref{thm:pnp}).
\item Reproducible experiments (Section~\ref{sec:experiments}): $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$.
\end{itemize}

Section~\ref{sec:algorithm} describes the algorithm, Section~\ref{sec:correctness} proves correctness, Section~\ref{sec:ratio} the bounds, Section~\ref{sec:conjecture} states the conjecture and its consequences, and Section~\ref{sec:runtime} the running time. Section~\ref{sec:experiments} reports the experiments and Section~\ref{sec:conclusion} concludes.

\section{Research Data}

The algorithm is implemented in the Python package \texttt{esperanza}, available on the Python Package Index~\cite{Vega26}. The version described in this paper is v0.1.6. Table~\ref{codeMetadata} lists the code metadata.

\begin{table}[!htbp]
\centering
\small
\begin{tabular}{|l|l|l|}
\hline
\textbf{Nr.} & \textbf{Code metadata description} & \textbf{Metadata} \\
\hline
C1 & Current code version & v0.1.6 \\
\hline
C2 & Permanent link to code/repository & \url{https://github.com/frankvegadelgado/esperanza} \\
\hline
C3 & Permanent link to Reproducible Capsule & \url{https://pypi.org/project/esperanza/} \\
\hline
C4 & Legal Code License & MIT License \\
\hline
C5 & Code versioning system used & git \\
\hline
C6 & Languages, tools, and services used & Python \\
\hline
C7 & Compilation requirements and dependencies & Python $\ge$ 3.12, Salvador $\ge$ 0.1.4 \\
\hline
C8 & Experiment scripts (Section~\ref{sec:experiments}) & \texttt{car/} directory of the repository \\
\hline
\end{tabular}
\caption{Code metadata for the \texttt{esperanza} package.}
\label{codeMetadata}
\end{table}

\section{The Esperanza Algorithm}
\label{sec:algorithm}

Algorithms~\ref{alg:main}--\ref{alg:lrs} give the pseudo-code of \textsc{Esperanza}; they follow the published implementation (version 0.1.6~\cite{Vega26}). Throughout, $G$ denotes the working graph obtained in Algorithm~\ref{alg:main} 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 \emph{tightness} of $v$ is $t_S(v)=|N(v)\cap S|$.

\begin{algorithm}[htbp]
\caption{\textsc{FindIndependentSet}$(G;\,B_{\mathrm R},B_{\mathrm L},B_{\mathrm I},\sigma)$}
\label{alg:main}
\begin{algorithmic}[1]
\Require Undirected graph $G=(V,E)$; work budgets $B_{\mathrm R},B_{\mathrm L},B_{\mathrm I}$ (default $100$ each); seed $\sigma$
\Ensure A maximal independent set of $G$
\If{$|V|=0$} \Return $\emptyset$ \EndIf
\State $G\gets G.\mathrm{copy}()$; remove all self-loops from $G$
\State $I_{\mathrm{iso}}\gets\{v\in V:\deg_G(v)=0\}$; remove $I_{\mathrm{iso}}$ from $G$
\If{$|V(G)|=0$} \Return $I_{\mathrm{iso}}$ \EndIf
\State $I_{\mathrm{CW}}\gets\textsc{PureCaroWeiBaseline}(G)$ \Comment{Algorithm~\ref{alg:carowei}}
\State $C\gets\textsc{Salvador}(G)$ \label{line:salvador} \Comment{\cite{Vega26SalvadorPaper,Vega26Salvador}; Lemma~\ref{lem:salvador}}
\State $S\gets I_{\mathrm{CW}}$ \textbf{if} $|I_{\mathrm{CW}}|>|V(G)\setminus C|$ \textbf{else} $V(G)\setminus C$
\State $v_{\max}\gets$ a vertex of maximum degree in $G$
\State $I_{\mathrm R}\gets V(G)\setminus\textsc{RefineCover}(G,C,v_{\max},B_{\mathrm R})$ \label{line:refine} \Comment{restarts from $C\cup\{v_{\max}\}$}
\If{$|I_{\mathrm R}|>|S|$} $S\gets I_{\mathrm R}$ \EndIf
\State $I_{\mathrm L}\gets\textsc{LocalRestartSearch}(G,S,B_{\mathrm L})$ \Comment{Algorithm~\ref{alg:lrs}}
\If{$|I_{\mathrm L}|>|S|$} $S\gets I_{\mathrm L}$ \EndIf
\State $I_{\mathrm I}\gets V(G)\setminus\textsc{ImproveVertexCover}(G,V(G)\setminus S,B_{\mathrm I},\sigma)$ \label{line:ils} \Comment{$(1,2)$-swaps~\cite{andrade2012fast}}
\If{$|I_{\mathrm I}|>|S|$} $S\gets I_{\mathrm I}$ \EndIf
\State $S\gets\textsc{MaximizeSolution}(G,S)$ \Comment{Algorithm~\ref{alg:maximize}}
\State \Return $S\cup I_{\mathrm{iso}}$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[htbp]
\caption{\textsc{PureCaroWeiBaseline}$(G)$: dynamic minimum-degree greedy}
\label{alg:carowei}
\begin{algorithmic}[1]
\Require Undirected graph $G=(V,E)$
\Ensure A maximal independent set $I$ with $|I|\ge\sum_{v}1/(\deg_G(v)+1)$
\State $\mathrm{deg}[v]\gets\deg_G(v)$ for every $v$; place every $v$ into bucket $B[\mathrm{deg}[v]]$; $\mathrm{ptr}\gets0$
\State $\mathrm{removed}\gets\emptyset$; $I\gets\emptyset$
\While{some vertex is not removed}
  \State advance $\mathrm{ptr}$ to the first bucket whose front is not removed, discarding removed fronts
  \State $v\gets$ pop front of $B[\mathrm{ptr}]$; $I\gets I\cup\{v\}$; mark $v$ removed
  \For{each neighbour $u$ of $v$ that is not removed}
    \State mark $u$ removed
    \For{each neighbour $w\ne v$ of $u$ that is not removed}
      \State $\mathrm{deg}[w]\gets\mathrm{deg}[w]-1$; append $w$ to $B[\mathrm{deg}[w]]$
      \If{$\mathrm{deg}[w]<\mathrm{ptr}$} $\mathrm{ptr}\gets\mathrm{deg}[w]$ \EndIf
    \EndFor
  \EndFor
\EndWhile
\State \Return $I$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[htbp]
\caption{\textsc{MaximizeSolution}$(G,S)$: repair and grow in $O(n+m)$}
\label{alg:maximize}
\begin{algorithmic}[1]
\Require Undirected graph $G=(V,E)$; candidate set $S\subseteq V$ (may contain conflicts)
\Ensure A maximal independent set of $G$
\State $I\gets S$; $\mathrm{conflicts}[u]\gets|N(u)\cap I|$ for $u\in I$
\For{each edge $\{u,v\}\in E$} \Comment{Phase 1: conflict resolution}
  \If{$u\in I$ \textbf{and} $v\in I$}
    \State $\ell\gets u$ \textbf{if} $\mathrm{conflicts}[u]\ge\mathrm{conflicts}[v]$ \textbf{else} $v$
    \State $I\gets I\setminus\{\ell\}$; decrement $\mathrm{conflicts}[w]$ for every $w\in N(\ell)\cap I$
  \EndIf
\EndFor
\State place every $u\notin I$ into the bucket $B[\deg_G(u)]$ \Comment{Phase 2: growth by counting sort}
\For{$d=0,\dots,\Delta$}
  \For{each $u\in B[d]$}
    \If{$N(u)\cap I=\emptyset$} $I\gets I\cup\{u\}$ \EndIf
  \EndFor
\EndFor
\State \Return $I$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[htbp]
\caption{\textsc{LocalRestartSearch}$(G,S,B)$: budgeted local restarts}
\label{alg:lrs}
\begin{algorithmic}[1]
\Require Graph $G$ without self-loops; independent set $S$; budget $B$
\Ensure An independent set $S'$ with $|S'|\ge|S|$
\State maintain $t(v)=|N(v)\cap S|$ for every $v$; $\mathrm{work}\gets$ cost of the initialisation; $\mathrm{limit}\gets\mathrm{work}+B(n+m)+1$
\State $Q\gets$ the vertices outside $S$, sorted by $(t(v),\deg v)$ with two counting sorts
\While{$Q\ne\emptyset$ \textbf{and} $\mathrm{work}\le\mathrm{limit}$}
  \State $u\gets Q.\textsc{PopFront}()$; $\mathrm{work}\gets\mathrm{work}+1$
  \If{$u\in S$} \textbf{continue} \EndIf
  \If{$t(u)=0$} insert $u$ into $S$; \textbf{continue} \EndIf
  \State $X\gets N(u)\cap S$; $T\gets\sum_{x\in X}\deg x$; $\mathrm{work}\gets\mathrm{work}+\deg u$
  \If{$\mathrm{work}+3(T+\deg u+|X|+1)+T\log_2(T+1)>\mathrm{limit}$} \textbf{continue} \EndIf
  \State remove every $x\in X$ from $S$; insert $u$ into $S$ \Comment{logged}
  \State $R\gets\{w\in N(X): w\notin S,\ t(w)=0\}$, sorted by $(\deg w, w)$
  \For{each $w\in R$} \If{$w\notin S$ \textbf{and} $t(w)=0$} insert $w$ into $S$ \Comment{logged} \EndIf \EndFor
  \If{$S$ grew} append to $Q$ every $w\in N(X)\setminus S$ not in $Q$ \Comment{commit}
  \Else\ undo the logged operations \EndIf
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

\paragraph{The calls to \textsc{Salvador}} Three routines of the package \texttt{salvador} (version $\ge0.1.4$)~\cite{Vega26Salvador} are used. \textsc{Salvador}$(G)$ in line~\ref{line:salvador} is \texttt{salvador.algorithm.find\_vertex\_cover}, the final cover of the seventeen-strategy ensemble of~\cite{Vega26SalvadorPaper}. \textsc{RefineCover}$(G,C,v_{\max},B)$ in line~\ref{line:refine} is \texttt{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 \textsc{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 \textsc{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)$. \textsc{ImproveVertexCover}$(G,C',B,\sigma)$ in line~\ref{line:ils} is \texttt{salvador.local\_search.improve\_vertex\_cover}: it improves the independent set $V\setminus C'$ by the $(1,2)$-swaps of Andrade, Resende and Werneck~\cite{andrade2012fast}, 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$ (\texttt{ILS\_SEED} $=20261031$ in the package), and its work is charged to a counter with limit $B(n+m)$.

\paragraph{Local restarts} Algorithm~\ref{alg:lrs} applies the restart of \textsc{RefineCover} to the incumbent $S$ instead of the \textsc{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.

\section{Correctness of the Algorithm}
\label{sec:correctness}

\begin{Lemma}
\label{lem:maximize}
For every $S'\subseteq V(G)$, \textsc{MaximizeSolution}$(G,S')$ returns a maximal independent set of $G$ that contains every vertex of $S'$ having no neighbour in $S'$. In particular, if $S'$ is independent, then $S'$ is contained in the output.
\end{Lemma}

\begin{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.
\end{proof}

\begin{Lemma}
\label{lem:carowei}
Algorithm~\ref{alg:carowei} returns a maximal independent set $I$ of $G$ that is produced by the minimum-degree greedy rule: every chosen vertex has minimum degree in the graph of the vertices not yet removed. Consequently $|I|\ge\sum_{v\in V}\frac1{\deg_G(v)+1}\ge\frac n{\Delta+1}$.
\end{Lemma}

\begin{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 $\mathrm{ptr}$ that is not removed has current degree at most $\mathrm{ptr}$, and every bucket below $\mathrm{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]}\frac1{\deg_G(u)+1}\le(d+1)\frac1{d+1}=1$. The closed neighbourhoods of the chosen vertices partition $V$, so $\sum_{v\in V}\frac1{\deg_G(v)+1}\le|I|$, and $\deg_G(v)\le\Delta$ gives the second inequality.
\end{proof}

\begin{Lemma}[Properties of the \textsc{Salvador} routines]
\label{lem:salvador}
Let $G$ be a graph without self-loops and isolated vertices.
\begin{enumerate}
\item[(i)] The cover $C$ of line~\ref{line:salvador} is a vertex cover with $|C|\le2\tau(G)-r(G)$, computed in $O((n+m)\,\alpha_{\mathrm A}(n))$ time~\cite{Vega26SalvadorPaper}.
\item[(ii)] \textsc{RefineCover} and \textsc{ImproveVertexCover} return vertex covers no larger than their input cover, in $O(B(n+m)+n+m)$ time for a budget $B$~\cite{Vega26SalvadorPaper,Vega26Salvador}.
\end{enumerate}
\end{Lemma}

\begin{proof}
(i) is the bound $2\tau-r$ and the running time proved for \textsc{Salvador} 0.1.4 in~\cite{Vega26SalvadorPaper}. For (ii), \textsc{RefineCover} returns either its input or a cover of the form $V\setminus I$ with $I$ independent and strictly larger than $V\setminus C$; \textsc{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~\cite{Vega26SalvadorPaper}, whose work counters stop after $B(n+m)$ units plus the cost of one step, which is $O(n+m)$.
\end{proof}

\begin{Lemma}
\label{lem:lrs}
For an independent set $S$ of a graph without self-loops, Algorithm~\ref{alg:lrs} returns an independent set $S'$ with $|S'|\ge|S|$.
\end{Lemma}

\begin{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.
\end{proof}

\begin{Theorem}
\label{thm:correctness}
Algorithm~\ref{alg:main} (\textsc{FindIndependentSet}) returns a maximal independent set of the input graph, where self-loops are ignored.
\end{Theorem}

\begin{proof}
$I_{\mathrm{CW}}$ is independent by Lemma~\ref{lem:carowei}. $V(G)\setminus C$, $I_{\mathrm R}$ and $I_{\mathrm I}$ are complements of vertex covers by Lemma~\ref{lem:salvador}, hence independent, and $I_{\mathrm L}$ is independent by Lemma~\ref{lem:lrs}. So the incumbent $S$ is independent before the last call, and \textsc{MaximizeSolution}$(G,S)$ returns a maximal independent set of the working graph by Lemma~\ref{lem:maximize}. 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$.
\end{proof}

\section{Proved Bounds}
\label{sec:ratio}

\begin{Theorem}[The complementary cover]
\label{thm:cover}
Let $G$ be a graph without self-loops, $S$ the set returned by Algorithm~\ref{alg:main} and $C$ the \textsc{Salvador} cover of line~\ref{line:salvador}. Then $V\setminus S$ is a vertex cover of $G$ and
\[
|V\setminus S|\ \le\ |C|\ \le\ 2\,\tau(G)-r(G).
\]
\end{Theorem}

\begin{proof}
$V\setminus S$ is a vertex cover because $S$ is independent (Theorem~\ref{thm:correctness}). The incumbent starts with at least $|V(G)\setminus C|$ vertices and is only replaced by larger sets; the final \textsc{MaximizeSolution} call keeps the incumbent, which is independent, by Lemma~\ref{lem:maximize}. Hence $|S|\ge|V(G)\setminus C|+|I_{\mathrm{iso}}|$, and $|V\setminus S|\le|C|$. Isolated vertices change neither $\tau$ nor $r$, so Lemma~\ref{lem:salvador}(i) gives $|C|\le2\tau(G)-r(G)$.
\end{proof}

The package exposes this cover as \texttt{esperanza.algorithm.find\_vertex\_cover}, which also adds every vertex with a self-loop.

\begin{Corollary}
\label{cor:dense}
For every graph $G$ without self-loops, $|S|\ge2\alpha(G)-n+r(G)$. Hence, if $\alpha(G)=\beta n$ with $\beta>\frac12$, then $\alpha(G)/|S|\le\beta/(2\beta-1)$.
\end{Corollary}

\begin{proof}
By Theorem~\ref{thm:cover}, $|S|\ge n-2\tau(G)+r(G)=n-2(n-\alpha(G))+r(G)$. For $\alpha=\beta n$ with $\beta>\frac12$ this gives $|S|\ge(2\beta-1)n$.
\end{proof}

\begin{Theorem}[Bounded degree]
\label{thm:degree}
For every graph $G$ of maximum degree $\Delta$, the set $S$ returned by Algorithm~\ref{alg:main} satisfies $|S|\ge\sum_v1/(\deg v+1)\ge n/(\Delta+1)$ and
\[
\frac{\alpha(G)}{|S|}\ \le\ \frac{\Delta+2}{3}.
\]
\end{Theorem}

\begin{proof}
The incumbent starts with at least $|I_{\mathrm{CW}}|$ vertices on the working graph and never shrinks (proof of Theorem~\ref{thm:cover}), 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~\ref{lem:carowei}), which has ratio at most $(\Delta+2)/3$ on graphs of maximum degree $\Delta$~\cite{halldorsson1994greedy}, and satisfies the Caro--Wei bound by Lemma~\ref{lem:carowei}.
\end{proof}

\begin{Theorem}[Ratio $O(\sqrt n)$ on four classes]
\label{thm:sqrt}
Let $G$ be a graph on $n$ vertices without self-loops and isolated vertices, $\alpha=\alpha(G)$, $C$ the \textsc{Salvador} cover of line~\ref{line:salvador} and $S$ the set returned by Algorithm~\ref{alg:main}. If at least one of the following conditions holds, then $\alpha/|S|\le2\sqrt n$:
\begin{enumerate}
\item[(a)] $\alpha\le2\sqrt n$;
\item[(b)] $2\alpha-n\ge\alpha/\sqrt n$;
\item[(c)] $|I^*\setminus C|\ge\alpha/\sqrt n$ for some maximum independent set $I^*$ of $G$;
\item[(d)] $\Delta\le\sqrt n$.
\end{enumerate}
\end{Theorem}

\begin{proof}
By the proofs of Theorems~\ref{thm:cover} and~\ref{thm:degree}, $|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~\ref{lem:salvador}(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~\ref{lem:carowei} and $\alpha\le n$,
\[
|S|\ \ge\ |I_{\mathrm{CW}}|\ \ge\ \frac n{\Delta+1}\ \ge\ \frac n{\sqrt n+1}\ \ge\ \frac{\sqrt n}2\ \ge\ \frac{\alpha}{2\sqrt 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$.
\end{proof}

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)<\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~\ref{conj:sqrt} in Section~\ref{sec:conjecture}. On general graphs, by~\cite{hastad1999clique,zuckerman2007linear}, a polynomial-time ratio of $n^{1-\varepsilon}$ for some $\varepsilon>0$ would imply $\mathrm{P}=\mathrm{NP}$.

\paragraph{The barrier $\Delta/\log^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\Delta)$ for all sufficiently large $\Delta$~\cite{austrin2011inapproximability}. Without any conjecture, Chan proved that the factor $O(\Delta/\log^4\Delta)$ is NP-hard~\cite{chan2016approximation}, and the best known polynomial-time ratio is $O(\Delta\log\log\Delta/\log\Delta)$~\cite{halperin2002improved}. Consequently, a polynomial-time algorithm whose ratio on graphs of maximum degree $\Delta$ is $o(\Delta/\log^2\Delta)$ as $\Delta\to\infty$ would refute the Unique Games Conjecture unless $\mathrm{P}=\mathrm{NP}$. The ratio $(\Delta+2)/3$ proved in Theorem~\ref{thm:degree} is linear in $\Delta$, so it lies above this threshold for large $\Delta$ and is consistent with both hardness results. Section~\ref{sec:bounded} reports the measured ratios of \textsc{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 \textsc{Esperanza} grows more slowly than $\Delta/\log^2\Delta$.

\section{The Conjectured Bounds and Their Consequences}
\label{sec:conjecture}

Let $M$ be the maximal matching returned by NetworkX's \texttt{min\_maximal\_matching}~\cite{hagberg2008exploring} on the working graph; it is the matching of the strategy $c_2$ of \textsc{Salvador}~\cite{Vega26SalvadorPaper}. 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|$.

\begin{Conjecture}[Esperanza bound]
\label{conj:esperanza}
For every graph $G$ without self-loops and isolated vertices, the set $S$ returned by Algorithm~\ref{alg:main} satisfies
\[
|V\setminus S|\ \le\ 2\,\tau(G)-|M|,\qquad\text{equivalently}\qquad |V\setminus S|-\tau(G)\ \le\ \tau(G)-|M|.
\]
\end{Conjecture}

\begin{Proposition}
\label{prop:implied}
Conjecture~\ref{conj:esperanza} is implied by the Ensemble-bound conjecture of~\cite{Vega26SalvadorPaper}, which states $|C|\le2\tau(G)-|M|$ for the \textsc{Salvador} cover $C$. If Conjecture~\ref{conj:esperanza} holds, then $|V\setminus S|\le\frac32\tau(G)$ for every graph.
\end{Proposition}

\begin{proof}
$|V\setminus S|\le|C|$ by Theorem~\ref{thm:cover}. The second statement follows from $|M|\ge\tau(G)/2$.
\end{proof}

\begin{Proposition}[Per-instance certificate]
\label{prop:cert}
Let $L\le\tau(G)\le U$ be a lower and an upper bound. If $|V\setminus S|\le2L-|M|$, then Conjecture~\ref{conj:esperanza} holds on $G$; if $|V\setminus S|>2U-|M|$, it fails on $G$. If $|V\setminus S|\le\frac32L$, then $|V\setminus S|\le\frac32\tau(G)$.
\end{Proposition}

\begin{proof}
$2L-|M|\le2\tau-|M|\le2U-|M|$, and $\frac32L\le\frac32\tau$.
\end{proof}

\begin{Proposition}[NO-type instances]
\label{prop:no}
If $G$ has no independent set of more than $\delta n$ vertices with $\delta\le\frac14$, then every vertex cover $C'$ of $G$ satisfies $|C'|\le2\tau(G)-|M|$. In particular, Conjecture~\ref{conj:esperanza} holds on the NO-type instances of the reduction of Khot and Regev~\cite{khot2008vertex} with $\delta\le\frac14$.
\end{Proposition}

\begin{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(\frac12-\delta)n\le\tau-|M|$.
\end{proof}

\begin{Theorem}[Conditional consequence]
\label{thm:pnp}
Assume that for every fixed $\varepsilon_0>0$ it is NP-hard to approximate Minimum Vertex Cover within $2-\varepsilon_0$. If Conjecture~\ref{conj:esperanza} is proved, then $\mathrm{P}=\mathrm{NP}$. The assumption holds if UGC holds~\cite{khot2008vertex}, and in particular if the theorem reported in~\cite{openai2026ugc} holds; without any assumption, a proof of Conjecture~\ref{conj:esperanza} would refute UGC unless $\mathrm{P}=\mathrm{NP}$.
\end{Theorem}

\begin{proof}
Algorithm~\ref{alg:main} runs in polynomial time (Theorem~\ref{thm:runtime}), and the function $G\mapsto V\setminus S$ returns a vertex cover. A proof of Conjecture~\ref{conj:esperanza} makes it a $\frac32$-approximation (Proposition~\ref{prop:implied}), a ratio of the form $2-\varepsilon_0$ with $\varepsilon_0=\frac12$, so under the assumption it solves an NP-hard problem in polynomial time. The theorem of Khot and Regev~\cite{khot2008vertex} derives the assumption from UGC.
\end{proof}

Theorem~\ref{thm:pnp} is a conditional implication, not a proof of $\mathrm{P}=\mathrm{NP}$. The theorem of~\cite{openai2026ugc} had not been peer reviewed at the time of writing; we cite it as reported and have not checked the formalization. By Proposition~\ref{prop:no}, a counterexample to Conjecture~\ref{conj:esperanza} with $\alpha\le n/4$ does not exist, so a counterexample has an independent set of more than a quarter of the vertices.

\begin{Conjecture}[Ratio $O(\sqrt n)$]
\label{conj:sqrt}
For every graph $G$ on $n$ vertices without self-loops, the set $S$ returned by Algorithm~\ref{alg:main} satisfies $\alpha(G)/|S|\le2\sqrt n$.
\end{Conjecture}

By Theorem~\ref{thm:sqrt}, Conjecture~\ref{conj:sqrt} 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).

\begin{Theorem}[Conditional consequence of Conjecture~\ref{conj:sqrt}]
\label{thm:sqrtpnp}
If Conjecture~\ref{conj:sqrt} is proved, then $\mathrm{P}=\mathrm{NP}$.
\end{Theorem}

\begin{proof}
Algorithm~\ref{alg:main} runs in polynomial time (Theorem~\ref{thm:runtime}). For $n\ge16$, $2\sqrt n\le n^{3/4}$, so Conjecture~\ref{conj:sqrt} would give a polynomial-time approximation of Maximum Independent Set within $n^{1-\varepsilon}$ with $\varepsilon=\frac14$, which is NP-hard~\cite{zuckerman2007linear}.
\end{proof}

\section{Runtime Analysis}
\label{sec:runtime}

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

\begin{Lemma}
\label{lem:lrs-time}
Algorithm~\ref{alg:lrs} runs in $O(B(n+m)+n+m)$ time.
\end{Lemma}

\begin{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 $\mathrm{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_2k$, and the requeueing costs $\sum_{x\in X}\deg x$. The loop runs only while $\mathrm{work}\le\mathrm{limit}=O(B(n+m)+n+m)$, and a move is started only if $\mathrm{work}$ plus the bound $3(T+\deg u+|X|+1)+T\log_2(T+1)$ is at most $\mathrm{limit}$. The bound covers every charge of the move except the insertions of refill vertices and their undo, 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 $\mathrm{work}$ exceeds $\mathrm{limit}$. Hence the total work is $O(B(n+m)+n+m)$.
\end{proof}

\begin{Theorem}[Running time]
\label{thm:runtime}
For fixed budgets $B_{\mathrm R},B_{\mathrm L},B_{\mathrm I}$, Algorithm~\ref{alg:main} runs in $O((n+m)\,\alpha_{\mathrm A}(n))$ expected time, where $\alpha_{\mathrm A}$ is the inverse Ackermann function; in general it runs in $O\bigl((n+m)(\alpha_{\mathrm A}(n)+B_{\mathrm R}+B_{\mathrm L}+B_{\mathrm I})\bigr)$ time.
\end{Theorem}

\begin{proof}
Copying the graph and removing self-loops and isolated vertices take $O(n+m)$ time. Algorithm~\ref{alg:carowei} 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. \textsc{Salvador} takes $O((n+m)\,\alpha_{\mathrm A}(n))$ time, and \textsc{RefineCover} and \textsc{ImproveVertexCover} take $O(B(n+m)+n+m)$ time each (Lemma~\ref{lem:salvador}). Building the adjacency lists, Algorithm~\ref{alg:lrs} (Lemma~\ref{lem:lrs-time}), Algorithm~\ref{alg:maximize}, the set differences and the comparisons take $O(B(n+m)+n+m)$ time.
\end{proof}

With the default budgets $B_{\mathrm R}=B_{\mathrm L}=B_{\mathrm I}=100$, the bound of Theorem~\ref{thm:runtime} is $O((n+m)\,\alpha_{\mathrm A}(n))$. Passing \texttt{restart\_budget=None} removes the cap of \textsc{RefineCover}, whose running time is then $O(|C|(n+m))$.

\section{Experiments}
\label{sec:experiments}

All experiments use Esperanza 0.1.6 and Salvador 0.1.4, and the three scripts of the folder \texttt{car/} of the repository: \texttt{experiment.py} (Section~\ref{sec:suite}), \texttt{ugc\_candidate.py} (Section~\ref{sec:kr}) and \texttt{bounded\_degree.py} (Section~\ref{sec:bounded}). The scripts import the repository's own \texttt{esperanza/}. Exact optima and bounds are computed with \texttt{scipy.optimize.milp}~\cite{virtanen2020scipy}, which calls the HiGHS solver~\cite{huangfu2018parallelizing}. The environment is Windows 11, Python 3.12.3 and NetworkX 3.6.1~\cite{hagberg2008exploring}; wall-clock times are machine dependent.

\subsection{Certified suite of 30\,000 graphs}
\label{sec:suite}

\emph{Instance generation.} A single master generator \texttt{random.Random(42)} is consumed in the order of Table~\ref{tab:families}. Each random graph receives its own seed, drawn as \texttt{randrange($2^{31}$)} from the master generator. The \texttt{amplified} family is built after the first six. Its bases are the connected \texttt{gnp} and \texttt{regular} instances with $n\le 12$, 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.

\begin{table}[htbp]
\centering
\small
\setlength{\tabcolsep}{4pt}
\caption{Instance families of the certified suite (master seed 42). $U\{a,\ldots,b\}$ is uniform on integers and $U(a,b)$ uniform on reals; all generators are NetworkX functions. The last two columns give the realised ranges of $n$ and $m$.}
\label{tab:families}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrllcc}
\toprule
Family & Count & Generator & Parameters & $n$ & $m$ \\
\midrule
\texttt{gnp} & 15000 & \texttt{gnp\_random\_graph}$(n,p)$ & $n\sim U\{6,\ldots,16\}$, $p\sim U(0.15,0.85)$ & 6--16 & 0--109 \\
\texttt{bipartite\_gnp} & 6000 & \texttt{bipartite.random\_graph}$(a,b,p)$ & $a,b\sim U\{3,\ldots,14\}$, $p\sim U(0.10,0.50)$ & 6--28 & 0--104 \\
\texttt{regular} & 3000 & \texttt{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 \\
\texttt{star} & 2000 & \texttt{star\_graph}$(k)$ & $k\sim U\{3,\ldots,80\}$ & 4--81 & 3--80 \\
\texttt{complete} & 1000 & \texttt{complete\_graph}$(n)$ & $n\sim U\{3,\ldots,30\}$ & 3--30 & 3--435 \\
\texttt{complete\_bipartite} & 1000 & \texttt{complete\_bipartite\_graph}$(a,b)$ & $a\sim U\{2,\ldots,12\}$, $b\sim U\{a,\ldots,20\}$ & 4--32 & 4--240 \\
\texttt{amplified} & 2000 & disjoint union or blow-up & see text & 12--96 & 16--1368 \\
\bottomrule
\end{tabular}%
}
\end{table}

\emph{Exact optimum.} For each instance we solve
\[
\max \sum_{v \in V} x_v \quad \text{subject to} \quad x_u + x_v \le 1 \ \ \forall \{u,v\} \in E, \qquad x_v \in \{0, 1\},
\]
with the default options of \texttt{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|$.

\emph{Results.} \textsc{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~\ref{tab:suite}), and the returned sets have $269\,247$ vertices in total. The complete run, including the integer programs, took $747.9$\,s.

\begin{table}[htbp]
\centering
\small
\caption{Certified suite: worst and mean ratio $\alpha(G)/|S|$ of \textsc{Esperanza} 0.1.6 per family.}
\label{tab:suite}
\begin{tabular}{lrrr}
\toprule
Family & Count & Worst & Mean \\
\midrule
\texttt{gnp} & 15000 & 1.000 & 1.000 \\
\texttt{bipartite\_gnp} & 6000 & 1.000 & 1.000 \\
\texttt{regular} & 3000 & 1.000 & 1.000 \\
\texttt{star} & 2000 & 1.000 & 1.000 \\
\texttt{complete} & 1000 & 1.000 & 1.000 \\
\texttt{complete\_bipartite} & 1000 & 1.000 & 1.000 \\
\texttt{amplified} & 2000 & 1.000 & 1.000 \\
\midrule
\textbf{All} & 30000 & 1.000 & 1.000 \\
\bottomrule
\end{tabular}
\end{table}

\subsection{YES-type instances of the Khot--Regev reduction}
\label{sec:kr}

The instances are those of Part~D of the \textsc{Salvador} experiments~\cite{Vega26SalvadorPaper}, 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~\cite{khot2008vertex}. The dictator set $\{(v,x):L(v)\in x\}$, made independent greedily on violated constraints, gives the \emph{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~\ref{prop:cert} as \emph{certified} ($|C|\le2L-|M|$), \emph{violated} ($|C|>2U-|M|$) or \emph{open}, for $C=V\setminus S$ (E) and for the \textsc{Salvador} cover (S). Table~\ref{tab:kr} reports the counts.

\begin{table}[htbp]
\centering
\scriptsize
\caption{Khot--Regev YES instances: classification of $|C|\le2\tau-|M|$ for \textsc{Esperanza} (E) and \textsc{Salvador} (S); ``E$<$S'' counts covers of \textsc{Esperanza} strictly smaller than the \textsc{Salvador} cover; ``Opt.'' counts optimal covers of \textsc{Esperanza}; ``$\frac32$'' counts covers with $|C|\le\frac32L$; the last two columns give the largest $|C|/L$ and the smallest $|S|/n$.}
\label{tab:kr}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrr}
\toprule
Family & Inst. & E cert. & E open & E viol. & S cert. & S open & S viol. & E$<$S & Opt. & $\frac32$ & max $|C|/L$ & min $|S|/n$ \\
\midrule
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 \\
\midrule
\textbf{All} & \textbf{40} & \textbf{38} & \textbf{2} & \textbf{0} & \textbf{38} & \textbf{2} & \textbf{0} & \textbf{2} & \textbf{19} & \textbf{40} & \textbf{1.1513} & \textbf{0.3812} \\
\bottomrule
\end{tabular}%
}
\end{table}

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 \texttt{kr\_p0.35\_N80\_r0} ($n=1\,280$), $|C|=776$, $|M|=574$ and $L=674$, so $2L-|M|=774$; on \texttt{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. \textsc{Esperanza} is strictly smaller than \textsc{Salvador} on two instances ($683$ against $707$ on \texttt{kr\_linear\_N80\_r0}, and $763$ against $766$ on \texttt{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 \texttt{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 $\frac32$ 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. \textsc{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.

\subsection{Bounded-degree graphs}
\label{sec:bounded}

The script \texttt{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 \textsc{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~\ref{tab:bounded}).

\begin{table}[htbp]
\centering
\scriptsize
\caption{Bounded-degree graphs ($n=256$ for \texttt{regular} and \texttt{planted}). ``$\Delta$ set'' is the degree of the setting ($d\,s$ for \texttt{kr}), $\Delta$ the largest measured maximum degree; ``Exact'' counts instances with $\alpha$ proved and ``Opt.'' those on which $S$ is optimal; ``up'' is $\alpha_{\mathrm{up}}/|S|$ and ``low'' is $\alpha_{\mathrm{low}}/|S|$; ``CW'' and ``Salv.'' are $\alpha_{\mathrm{up}}/|I|$ for the Caro--Wei baseline and the complement of the \textsc{Salvador} cover; ``norm.'' is the largest $(\alpha_{\mathrm{up}}/|S|)/(\Delta/\log_2^2\Delta)$.}
\label{tab:bounded}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrr}
\toprule
Family & $\Delta$ set & $\Delta$ & Inst. & Exact & Opt. & max up & mean up & max low & CW & Salv. & $\Delta/\log_2^2\Delta$ & norm. \\
\midrule
\texttt{kr} & 12 & 12 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 1.0134 & 1.0000 & 0.9337 & 1.0710 \\
\texttt{kr} & 24 & 24 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 1.0714 & 1.0000 & 1.1417 & 0.8759 \\
\texttt{kr} & 32 & 32 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 1.0246 & 1.0000 & 1.2800 & 0.7812 \\
\texttt{kr} & 64 & 64 & 2 & 2 & 1 & 1.0086 & 1.0043 & 1.0086 & 1.0636 & 1.0086 & 1.7778 & 0.5673 \\
\texttt{planted} & 4 & 4 & 2 & 1 & 1 & 1.0577 & 1.0288 & 1.0000 & 1.1500 & 1.0577 & 1.0000 & 1.0577 \\
\texttt{planted} & 8 & 8 & 2 & 1 & 1 & 1.0769 & 1.0385 & 1.0000 & 1.1136 & 1.0769 & 0.8889 & 1.2115 \\
\texttt{planted} & 16 & 16 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 1.6667 & 1.0000 & 1.0000 & 1.0000 \\
\texttt{planted} & 32 & 32 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 2.3077 & 1.0000 & 1.2800 & 0.7812 \\
\texttt{planted} & 64 & 62 & 2 & 2 & 2 & 1.0000 & 1.0000 & 1.0000 & 1.0000 & 1.0000 & 1.7488 & 0.5815 \\
\texttt{regular} & 3 & 3 & 1 & 1 & 0 & 1.0088 & 1.0088 & 1.0088 & 1.0270 & 1.0088 & 1.1942 & 0.8448 \\
\texttt{regular} & 4 & 4 & 1 & 0 & 0 & 1.0476 & 1.0476 & 1.0000 & 1.1224 & 1.0476 & 1.0000 & 1.0476 \\
\texttt{regular} & 5 & 5 & 1 & 0 & 0 & 1.0947 & 1.0947 & 1.0000 & 1.1556 & 1.0947 & 0.9274 & 1.1804 \\
\texttt{regular} & 6 & 6 & 1 & 0 & 0 & 1.1705 & 1.1705 & 1.0000 & 1.1839 & 1.1705 & 0.8979 & 1.3035 \\
\texttt{regular} & 8 & 8 & 1 & 0 & 0 & 1.2436 & 1.2436 & 1.0000 & 1.3288 & 1.2436 & 0.8889 & 1.3990 \\
\texttt{regular} & 12 & 12 & 1 & 0 & 0 & 1.4194 & 1.4194 & 1.0000 & 1.4915 & 1.4194 & 0.9337 & 1.5201 \\
\texttt{regular} & 16 & 16 & 1 & 0 & 0 & 1.5283 & 1.5283 & 1.0000 & 1.5882 & 1.5283 & 1.0000 & 1.5283 \\
\texttt{regular} & 24 & 24 & 1 & 0 & 0 & 1.6429 & 1.6429 & 1.0000 & 1.7692 & 1.6429 & 1.1417 & 1.4390 \\
\texttt{regular} & 32 & 32 & 1 & 0 & 0 & 1.8788 & 1.8788 & 1.0000 & 2.0667 & 1.8788 & 1.2800 & 1.4678 \\
\texttt{regular} & 48 & 48 & 1 & 0 & 0 & 2.0800 & 2.0800 & 1.0000 & 2.3636 & 2.0800 & 1.5389 & 1.3516 \\
\texttt{regular} & 64 & 64 & 1 & 0 & 0 & 2.2500 & 2.2500 & 1.0000 & 2.5000 & 2.2500 & 1.7778 & 1.2656 \\
\texttt{regular} & 96 & 96 & 1 & 0 & 0 & 2.4286 & 2.4286 & 1.0000 & 2.8333 & 2.4286 & 2.2139 & 1.0969 \\
\texttt{regular} & 128 & 128 & 1 & 0 & 0 & 2.4545 & 2.4545 & 1.0000 & 3.3750 & 2.4545 & 2.6122 & 0.9396 \\
\bottomrule
\end{tabular}%
}
\end{table}

On the \texttt{kr} and \texttt{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 \texttt{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 \textsc{Salvador} cover. \textsc{Esperanza} took at most $1.48$\,s per instance, and the whole run $908.8$\,s.

\section{Conclusion}
\label{sec:conclusion}

\textsc{Esperanza} 0.1.6 returns a maximal independent set (Theorem~\ref{thm:correctness}) in $O((n+m)\,\alpha_{\mathrm A}(n))$ expected time for fixed work budgets (Theorem~\ref{thm:runtime}). Its complementary vertex cover has at most $2\tau-r$ vertices (Theorem~\ref{thm:cover}), and on graphs of maximum degree $\Delta$ its ratio is at most $(\Delta+2)/3$ (Theorem~\ref{thm:degree}), above the UGC-hardness threshold $O(\Delta/\log^2\Delta)$ of~\cite{austrin2011inapproximability}; its ratio is at most $2\sqrt n$ on every graph with $\Delta\le\sqrt n$ and on the further classes of Theorem~\ref{thm:sqrt}. 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 \textsc{Esperanza} has ratio $O(\sqrt n)$ on every graph; this is Conjecture~\ref{conj:sqrt}, and a proof would imply $\mathrm{P}=\mathrm{NP}$ (Theorem~\ref{thm:sqrtpnp}). Nor do we claim that \textsc{Esperanza} is a $\frac32$-approximation for Minimum Vertex Cover. The bound $|V\setminus S|\le2\tau-|M|$ is a conjecture (Conjecture~\ref{conj:esperanza}); the experiments concern graphs of at most $2\,560$ vertices; and a proof would refute UGC unless $\mathrm{P}=\mathrm{NP}$, and would imply $\mathrm{P}=\mathrm{NP}$ if the theorem reported in~\cite{openai2026ugc} holds (Theorem~\ref{thm:pnp}). What is guaranteed on a given graph is the per-instance certificate of Proposition~\ref{prop:cert}. The implementation is freely available as the \texttt{esperanza} package on PyPI~\cite{Vega26}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgements}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Statements and Declarations}

\subsection*{Declaration of interests}

The author declares no competing interests.

\subsection*{Funding sources}

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

\subsection*{Declaration of generative AI in scientific writing}

The author designed the strategies of \textsc{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.

\subsection*{Data availability}

Code and data: \url{https://github.com/frankvegadelgado/esperanza} (release \texttt{v0.1.6}); the experiments of Section~\ref{sec:experiments} are reproduced by running the scripts of \texttt{car/}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{elsarticle-num}
\bibliography{biblio}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}