%% \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{An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm} \author{Frank Vega} \address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA} \ead{vega.frank@gmail.com} \begin{abstract} Minimum Vertex Cover has a classical linear-time ratio of $2$, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below $2$ unless $\mathrm{P}=\mathrm{NP}$. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in $O((n+m)\,\alpha(n))$ time, and that the returned cover has at most $2\tau-r$ vertices, where $r$ is the number of components with an edge, so the ratio is at most $1.999999999$ whenever $\tau\le10^{9}r$. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most $2L-|M|$ vertices, for a lower bound $L\le\tau$ and the maximal matching $M$, is within ratio $3/2$ on that instance. In a reproducible suite the returned cover satisfies $|C|\le2\tau-|M|$ on all $291$ tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the $68$ DIMACS clique complements it is never worse than Hvala and optimal on $37$ instances against $18$. Whether $|C|\le2\tau-|M|$ holds on every graph is stated as a conjecture: a proof would give a linear-time $3/2$-approximation and would refute the Unique Games Conjecture unless $\mathrm{P}=\mathrm{NP}$. \end{abstract} \begin{keyword} Vertex Cover \sep Approximation Algorithm \sep Maximal Matching \sep Split Graph \sep Bipartite Layers \sep Ensemble Heuristics \sep Linear Time \sep Unique Games Conjecture \sep P versus NP \MSC[2020] 05C69 \sep 05C70 \sep 68Q25 \sep 90C27 \end{keyword} \end{frontmatter} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} The \textbf{Minimum Vertex Cover} (VC) problem is one of the twenty-one NP-complete problems identified by Karp~\cite{karp2009reducibility}. Given an undirected graph $G=(V,E)$, a set $C\subseteq V$ is a \emph{vertex cover} if every edge has at least one endpoint in $C$; the goal is a cover of minimum size $\tau(G)$. We write $n=|V|$, $m=|E|$, $\nu(G)$ for the matching number, and $r(G)$ for the number of connected components of $G$ that have an edge. The approximation landscape is well charted. Both endpoints of a maximal matching form a $2$-approximation computable in linear time~\cite{papadimitriou1998combinatorial}, and LP-based refinements reach $2-\Theta(1/\sqrt{\log n})$~\cite{karakostas2009better,karpinski1996approximating}, which is $2-o(1)$ but not a constant below $2$. On the hardness side, Dinur and Safra ruled out ratios below $10\sqrt5-21\approx1.3606$ unless $\mathrm{P}=\mathrm{NP}$~\cite{dinur2005hardness}, and the proof of the $2$-to-$2$ Games Theorem raised this unconditional threshold to $\sqrt2-\varepsilon$~\cite{khot2018pseudorandom}. Under the Unique Games Conjecture (UGC)~\cite{khot2002unique}, Khot and Regev showed that no fixed ratio $2-\varepsilon$ is achievable in polynomial time unless $\mathrm{P}=\mathrm{NP}$~\cite{khot2008vertex}, and Austrin, Khot and Safra refined this to graphs of bounded degree~\cite{austrin2011inapproximability}, matching Halperin's algorithm~\cite{halperin2002improved}. The barrier persists on triangle-free graphs. Every vertex cover contains at least two vertices of each triangle, so taking all three vertices of a triangle and deleting them, until no triangle is left, and then running a $(2-\varepsilon)$-approximation for triangle-free graphs on the rest would approximate every graph within $\max\{3/2,\,2-\varepsilon\}$. Hence approximating Minimum Vertex Cover within $2-\varepsilon$ on triangle-free graphs is UGC-hard, as observed by Bonnet and Rz\k{a}\.{z}ewski~\cite{bonnet2025string}, who also note that for graphs of girth at least $5$ neither a $(2-\varepsilon)$-approximation nor a UGC-hardness proof is known. 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, every fixed ratio below $2$ is NP-hard, and in particular so is the ratio $3/2$, which lies above the unconditional threshold $\sqrt2$ but below $2$. \textsc{Salvador} is an ensemble algorithm, implemented in the Python package \texttt{Salvador}~\cite{Vega26Salvador}, that computes seventeen strategies $c_1,\dots,c_{17}$ in linear time and returns the smallest refined cover. The strategies are numbered in the order in which they are computed. The twelve \emph{base strategies} $c_1,\dots,c_{12}$ build covers from the graph: component amplification before a maximal matching ($c_1$), the maximal matching itself ($c_2$), degree and weight heuristics ($c_3$ to $c_6$), three reductions to auxiliary problems that are solved exactly ($c_7$, $c_8$ and $c_{10}$), a decomposition into bipartite layers ($c_9$), a weighted subdivision reduction with exact reductions and folding ($c_{11}$), and a bounded-treewidth dynamic program ($c_{12}$). The five \emph{improvers} $c_{13},\dots,c_{17}$ work on the covers already found: a union pass, a $(1,2)$-swap local search, a search that alternates with exact reductions, consensus forcing and a final swap-maximize refinement of every candidate. Three of the base strategies and the pruning pass adapt the published Hvala ensemble~\cite{Vega26Hvala,Vega26HvalaPyPI}, so \textsc{Salvador} contains Hvala and inherits its worst-case ratio $2$. The guarantees of the ensemble come from different strategies on different graphs. The maximal matching $c_2$ gives a cover of at most $2\tau-r$ vertices on every graph (Theorem~\ref{thm:twotau}), because every component with an edge saves one vertex. The component amplification $c_1$ uses this observation in the other direction: it creates components before matching. Every vertex $u$ has two copies $(u,0)$ and $(u,1)$; an edge of the maximal matching $M$ whose endpoints both have index $0$ is split off as an isolated edge, and the other edges of its endpoints move to the copies of index $1$. Splitting stops when the split graph has $r'$ components, the largest value not above $|M|$, so that $|M|-1\le r'\le|M|\le\tau$. The bipartite layers $c_9$ handle odd cycles differently: a non-bipartite component is split into at most $\lfloor\log_2m\rfloor+1$ bipartite layers, each solved by a matching, a few Hopcroft--Karp phases and K\H{o}nig's theorem, and a vertex chosen in one layer is discarded from the later ones. Minimum-degree rules make $c_5$ and $c_8$ exact on every regular bipartite graph, a Caro--Wei argument bounds $c_8$ on every graph, and the exact reductions and dynamic programs of $c_{10}$, $c_{11}$ and $c_{12}$ certify their own optimality whenever their cores are empty. \paragraph{Contributions} The main contributions of this paper are: \begin{itemize} \item The ensemble of seventeen strategies (Section~\ref{sec:algorithm}, Algorithm~\ref{alg:main}), with the component amplification $c_1$ (Algorithms~\ref{alg:split} and~\ref{alg:c1}, Figure~\ref{fig:split}) and the bipartite layers $c_9$ (Algorithm~\ref{alg:c9}, Figure~\ref{fig:layers}). \item Linear running time: with the default parameters every strategy, and therefore the whole ensemble, runs in $O((n+m)\,\alpha(n))$ time, with $\alpha$ the inverse Ackermann function (Theorem~\ref{thm:runtime}). \item A bound for every graph: the returned cover satisfies $|C|\le2\tau(G)-r(G)$ (Theorem~\ref{thm:twotau}); hence the ratio is at most $1.999999999$ on every graph with $\tau\le10^{9}r$, in particular on every graph with at most $10^{9}+1$ vertices (Corollary~\ref{cor:billion}). The margin $r/\tau$ tends to $0$ as $\tau$ grows, so this is not a $(2-\varepsilon)$-approximation. \item Per-class guarantees (Section~\ref{sec:perclass}): $c_5$ is exact on forests, cycles, complete and complete bipartite graphs (Theorem~\ref{thm:mtm-exact}); $c_5$ and $c_8$ are exact on every regular or degree-separated bipartite graph (Theorem~\ref{thm:degsep}); $c_8$ meets the Caro--Wei bound, hence ratio $2-2/(d+1)$ on $d$-regular graphs (Lemma~\ref{lem:carowei}, Theorem~\ref{thm:regular}); $c_3$ achieves $11/6$ on subcubic graphs (Theorem~\ref{thm:greedy}); $c_4$ satisfies a Cauchy--Schwarz bound (Theorem~\ref{thm:hallelujah}); $c_9$ uses at most $\lfloor\log_2m\rfloor+1$ layers and is a minimum cover of every bipartite component on which its phases reach a maximum matching (Proposition~\ref{prop:c9}); and a combined certificate with an exact a-posteriori form on the residue $\mathcal{R}$ of nearly K\H{o}nig--Egerv\'ary graphs (Theorems~\ref{thm:combined} and~\ref{thm:posterior}). \item The split graph of $c_1$: its component count is computed for every number of splits in one union-find pass, and $r(G)\le r'\le|M|\le\tau$ with $r'\ge|M|-1$ (Lemmas~\ref{lem:split} and~\ref{lem:rprime}). \item A per-instance $3/2$ certificate (Proposition~\ref{prop:cert}): any cover with $|C|\le2L-|M|$ or $|C|\le\frac32L$, for a computable lower bound $L\le\tau$, is within ratio $3/2$ of the optimum on that instance; and the conjecture that the returned cover always satisfies $|C|\le2\tau-|M|$ (Conjecture~\ref{conj:ensemble}), with the conditional theorem that a proof would refute UGC unless $\mathrm{P}=\mathrm{NP}$, and would imply $\mathrm{P}=\mathrm{NP}$ if the theorem of~\cite{openai2026ugc} holds (Theorem~\ref{thm:pnp}). \item A reproducible experimental suite (Section~\ref{sec:suite}): small graphs with known optima, large adversarial graphs with certified bounds, a strategy report and an ablation, bipartite, Khot--Regev YES-type, regular and triangle-free graphs, a study of the bags of $c_{10}$, a test of the conjectured bound and of the layers of $c_9$, a comparison with Hvala on the $68$ DIMACS clique complements, and the running time. \end{itemize} Section~\ref{sec:algorithm} describes the algorithm. Section~\ref{sec:correctness} proves correctness, Section~\ref{sec:approx} the approximation results, and Section~\ref{sec:runtime} the running time. Section~\ref{sec:suite} reports the experiments, and Section~\ref{sec:conclusion} concludes. \section{Research Data} The algorithm is implemented in the Python package \texttt{Salvador}, freely available on the Python Package Index~\cite{Vega26Salvador}. The version described in this paper is v0.1.4. Code metadata is summarised in Table~\ref{codeMetadata}. \begin{table}[!htbp] \centering \resizebox{\textwidth}{!}{% \begin{tabular}{|l|l|l|} \hline \textbf{Nr.} & \textbf{Code metadata description} & \textbf{Metadata} \\ \hline C1 & Current code version & v0.1.4 \\ \hline C2 & Permanent link to code repository & \url{https://github.com/frankvegadelgado/salvador} \\ \hline C3 & Permanent link to reproducible capsule & \url{https://pypi.org/project/salvador/} \\ \hline C4 & Legal Code License & MIT License \\ \hline C5 & Code versioning system used & git \\ \hline C6 & Languages, tools, and services used & Python $\geq 3.12$, NetworkX $\geq 3.4.2$, NumPy $\geq 2.2.1$, SciPy $\geq 1.15.0$ \\ \hline C7 & Compilation requirements and dependencies & Python, NetworkX, NumPy, SciPy \\ \hline \end{tabular}% } \caption{Code metadata for the \texttt{Salvador} package (v0.1.4).} \label{codeMetadata} \end{table} \section{Description of the Algorithm} \label{sec:algorithm} \subsection{Main ensemble} \textsc{Salvador}'s entry point, \textsc{FindVertexCover} (Algorithm~\ref{alg:main}), removes self-loops and isolated vertices and then computes the strategies in their numbering order. The base strategies $c_1,\dots,c_9$ are computed from the graph alone; $c_{10}$, $c_{11}$ and $c_{12}$ also receive the best cover found before them, which they use on the parts of the graph that their exact methods do not reach; the improvers $c_{13},\dots,c_{16}$ combine or improve the covers already found; and $c_{17}$ refines every candidate $c_1,\dots,c_{16}$ and returns the smallest refined cover. \begin{algorithm}[!htbp] \caption{\textsc{FindVertexCover}$(G)$ --- \textsc{Salvador} 0.1.4} \label{alg:main} \begin{algorithmic}[1] \Require Undirected graph $G=(V,E)$ \Ensure A vertex cover $C\subseteq V$ \State remove all self-loops and isolated vertices from $G$; \textbf{if} $E=\emptyset$ \textbf{return} $\emptyset$ \State $\mathit{adj}\gets\{v\mapsto N_G(v)\}$ \Comment{base strategies} \State $c_1\gets\textsc{ComponentSplitCover}(G)$ \Comment{Algorithm~\ref{alg:c1}} \State $c_2\gets\textsc{MaximalMatchingCover}(G)$; $c_3\gets\textsc{BucketDegreeGreedy}(\mathit{adj})$; $c_4\gets\textsc{Hallelujah}(G)$ \State $c_5\gets\textsc{MinToMinCover}(\mathit{adj})$; $c_6\gets\textsc{LinearWeightedCover}(G)$; $c_7\gets\textsc{SolveVC}(G)$ \State $c_8\gets\textsc{BipartitePlanarCover}(\mathit{adj})$; $c_i\gets\textsc{Prune}(\mathit{adj},c_i)$ for $i=2,\dots,8$ \State $c_9\gets\textsc{Prune}(\mathit{adj},\textsc{BipartiteLayersCover}(\mathit{adj}))$ \Comment{Algorithm~\ref{alg:c9}} \State $c_{10}\gets\textsc{EDSTreewidthCover}(\mathit{adj},\arg\min_{i\le9}|c_i|)$ \Comment{bipartite components} \State $c_{11}\gets\textsc{SubdivisionCover}(\mathit{adj},\arg\min_{i\le10}|c_i|)$ \State $c_{12}\gets\textsc{TreewidthDPCover}(\mathit{adj},\arg\min_{i\le11}|c_i|)$ \State $c_{13}\gets\textsc{Prune}(\mathit{adj},c_2\cup\dots\cup c_8)$ \Comment{improvers} \State $c_{14}\gets\textsc{LocalSearchCover}(\mathit{adj},\arg\min_{i\le13}|c_i|)$ \State $c_{15}\gets\textsc{ReduceSearchCover}(\mathit{adj},\arg\min_{i\le14}|c_i|)$ \State $c_{16}\gets\textsc{ConsensusForceCover}(\mathit{adj},\{c_1,\dots,c_{15}\})$ \State $v_{\max}\gets$ a vertex of maximum degree \State $c_{17}\gets\arg\min_{1\le i\le16}|\textsc{RefineCover}(G,c_i,v_{\max})|$ \State \Return $c_{17}$ \end{algorithmic} \end{algorithm} Every strategy that receives an earlier cover is guarded: $c_{10}$, $c_{12}$, $c_{14}$ and $c_{15}$ are replaced by the cover they start from whenever that cover is smaller, $c_{16}$ returns the smallest cover of its pool, and the refinement never enlarges a cover. Every candidate is pruned by Algorithm~\ref{alg:prune}, which removes in one pass every vertex whose neighbours all lie in the current set. \begin{algorithm}[!htbp] \caption{\textsc{Prune}$(\mathit{adj},C)$} \label{alg:prune} \begin{algorithmic}[1] \Require Adjacency map $\mathit{adj}$, a vertex cover $C$ \Ensure A vertex cover $C'\subseteq C$ \State $C'\gets C$ \For{$v$ in a fixed snapshot of $C$} \If{$N_G(v)\subseteq C'$} $C'\gets C'\setminus\{v\}$ \EndIf \EndFor \State \Return $C'$ \end{algorithmic} \end{algorithm} \subsection{Base strategies} \label{sec:strategies} Throughout, $G$ has no self-loops and no isolated vertices, $M$ is the maximal matching returned by the NetworkX routine \texttt{min\_maximal\_matching}, which builds a maximal matching greedily in one scan of the edges, and $\mathrm{pos}(u)$ is the position of $u$ in the vertex order of $G$, used to break ties. The same NetworkX routine is the only maximal-matching subroutine of every strategy. \paragraph{Component amplification: $c_1$.} The nodes of the \emph{split graph} $H$ are \emph{copies} $(u,i)$ of vertices $u$ of $G$ with an \emph{index} $i\in\{0,1\}$. Initially $H$ has the copy $(u,0)$ of every vertex and the edge $((u,0),(v,0))$ for every edge $\{u,v\}$ of $G$; the \emph{projection} $\pi(u,i)=u$ maps the edges of $H$ onto the edges of $G$. To \emph{split} an edge $((u,0),(v,0))$ whose endpoints both have index $0$, the edge is kept, every other edge of $(u,0)$ moves to $(u,1)$, and every other edge of $(v,0)$ moves to $(v,1)$; the split edge becomes an isolated $K_2$ of $H$ (Figure~\ref{fig:split}(a)). Only edges with index $0$ at both endpoints are split, and every vertex is an endpoint of at most one split edge, so no index larger than $1$ is ever needed and no bridge has to be found. The edges split are those of $M$, in the order of the scan: they are pairwise disjoint, so when an edge of $M$ comes up both its endpoints still have index $0$. Splitting the first $k$ edges $F_k$ of $M$ leaves the split graph with \[ \mathrm{count}(k)\ =\ k+c(G-F_k) \] components that have an edge, where $c(\cdot)$ counts the components with an edge: the $k$ split edges are isolated, and every other edge of $G$ keeps its endpoints connected through the copies of index $1$. Algorithm~\ref{alg:split} computes all the values $\mathrm{count}(0),\dots,\mathrm{count}(|M|)$ in one backward pass of a union-find structure, starting from $G-F_{|M|}$ and adding the edges of $M$ back one by one, and stops at the first $k$ at which $\mathrm{count}(k)$ reaches the largest value that does not exceed $|M|$. Lemma~\ref{lem:rprime} shows that this value $r'$ satisfies $r(G)\le r'\le|M|$ and $r'\ge|M|-1$. \begin{algorithm}[!htbp] \caption{\textsc{SplitGraph}$(G,M)$} \label{alg:split} \begin{algorithmic}[1] \Require Graph $G$ without isolated vertices, the maximal matching $M=(e_1,\dots,e_{|M|})$ of $G$ \Ensure Split graph $H$ with copies of index $0$ and $1$, and $r'$ components with an edge \State $\mathit{UF}\gets$ union-find over $V$ with the edges $E\setminus M$; $c\gets$ its trees that contain an edge \State $\mathrm{count}(|M|)\gets|M|+c$ \For{$k=|M|-1$ \textbf{down to} $0$} \State join the endpoints of $e_{k+1}$ in $\mathit{UF}$ and update $c$; \quad $\mathrm{count}(k)\gets k+c$ \EndFor \State $r'\gets\max\{\mathrm{count}(k):\mathrm{count}(k)\le|M|\}$; \quad $k^\ast\gets\min\{k:\mathrm{count}(k)=r'\}$ \State $S\gets$ the endpoints of $e_1,\dots,e_{k^\ast}$ \State $H\gets$ the edges $((u,0),(v,0))$ for $uv\in\{e_1,\dots,e_{k^\ast}\}$, and $((u,[u\in S]),(v,[v\in S]))$ for every other $uv\in E$ \State \Return $H$, $r'$ \end{algorithmic} \end{algorithm} \begin{figure}[!htbp] \centering \begin{tikzpicture}[ cp/.style={circle,draw,thick,minimum size=9mm,inner sep=0pt,font=\scriptsize}, kept/.style={line width=1.8pt,red!70!black}, e/.style={thick}, lbl/.style={font=\small}] \begin{scope} \node[cp] (u) at (0,0) {$(u,0)$}; \node[cp] (v) at (2.0,0) {$(v,0)$}; \node[cp] (a) at (-1.3,1.1) {$(a,0)$}; \node[cp] (b) at (-1.3,-1.1) {$(b,1)$}; \node[cp] (c) at (3.3,1.1) {$(c,0)$}; \node[cp] (d) at (3.3,-1.1) {$(d,0)$}; \draw[e] (u)--(a) (u)--(b) (v)--(c) (v)--(d); \draw[kept] (u)--(v); \node[lbl] at (1.0,-2.1) {before the split of $(u,0)(v,0)$}; \end{scope} \draw[-{Stealth[length=3mm]},thick] (4.2,0) -- (5.2,0); \begin{scope}[shift={(6.9,0)}] \node[cp] (u2) at (0,0.6) {$(u,0)$}; \node[cp] (v2) at (2.0,0.6) {$(v,0)$}; \node[cp,fill=blue!10] (u3) at (-0.3,-1.0) {$(u,1)$}; \node[cp,fill=blue!10] (v3) at (2.3,-1.0) {$(v,1)$}; \node[cp] (a2) at (-1.6,0.4) {$(a,0)$}; \node[cp] (b2) at (-1.6,-1.9) {$(b,1)$}; \node[cp] (c2) at (3.6,0.4) {$(c,0)$}; \node[cp] (d2) at (3.6,-1.9) {$(d,0)$}; \draw[kept] (u2)--(v2); \draw[e] (u3)--(a2) (u3)--(b2) (v3)--(c2) (v3)--(d2); \node[lbl] at (1.0,-2.6) {after: an isolated $K_2$ and the copies of index $1$}; \end{scope} \begin{scope}[shift={(0,-5.2)}] \node[cp] (pa) at (0,0) {$(a,0)$}; \node[cp] (pb) at (1.5,0) {$(b,0)$}; \node[cp] (pc) at (3.0,0) {$(c,0)$}; \node[cp] (pd) at (4.5,0) {$(d,0)$}; \node[cp] (pe) at (6.0,0) {$(e,0)$}; \draw[e] (pa)--(pb)--(pc)--(pd)--(pe); \node[lbl,align=center] at (3.0,-1.0) {$H$ of the path $a\,b\,c\,d\,e$ before splitting: $r=1$, $M=(ab,cd)$, target $|M|=2$}; \end{scope} \begin{scope}[shift={(0,-7.6)}] \node[cp] (qa) at (0,0) {$(a,0)$}; \node[cp] (qb) at (1.5,0) {$(b,0)$}; \node[cp,fill=blue!10] (qb1) at (3.0,0) {$(b,1)$}; \node[cp] (qc) at (4.5,0) {$(c,0)$}; \node[cp] (qd) at (6.0,0) {$(d,0)$}; \node[cp] (qe) at (7.5,0) {$(e,0)$}; \draw[kept] (qa)--(qb); \draw[kept] (qb1)--(qc); \draw[e] (qc)--(qd); \draw[kept] (qd)--(qe); \node[lbl,align=center] at (3.75,-1.15) {split of $ab$: $\mathrm{count}(1)=1+c(G-ab)=2=|M|$; a maximal matching of $H$ (thick) decodes\\ to $b$ and $d$ from the equal-index edges $ab$ and $de$, and $((b,1),(c,0))$ is then already covered}; \end{scope} \node[lbl] at (-1.6,1.9) {(a)}; \node[lbl] at (-1.6,-4.4) {(b)}; \end{tikzpicture} \caption{Strategy $c_1$. (a) Splitting $(u,0)(v,0)$ keeps it as an isolated $K_2$ and moves the other edges of $u$ and $v$ to their copies of index $1$ (shaded); only edges whose endpoints both have index $0$ are split. (b) The path $a\,b\,c\,d\,e$, with $\tau=2$. The maximal matching $M=(ab,cd)$ fixes the target $|M|=2$, and one split, of $ab$, reaches it. The matched edges $(a,0)(b,0)$ and $(d,0)(e,0)$ have equal indices and select their endpoint of larger degree in $G$, $b$ and $d$; the matched edge $((b,1),(c,0))$ is then covered by $b$. The decoded set $\{b,d\}$ is a minimum cover.} \label{fig:split} \end{figure} Let $M_H$ be the maximal matching of $H$ returned by \texttt{min\_maximal\_matching}; it contains every isolated $K_2$, because such an edge has no neighbouring edge. Every matched edge is written $((a,i),(b,j))$ with $(i,\mathrm{pos}(a))\le(j,\mathrm{pos}(b))$, and the edges are processed in increasing order of $(i,j)$ and then of $\mathrm{pos}(a)$, by a counting sort. A vertex is selected through at most one of its copies: an edge with an endpoint already selected adds nothing. An edge with $i=j$ selects its endpoint of larger degree in $G$, ties by position; with only two indices no residual graph is needed. An edge with $i=Latex ] % Original core edge, displayed above the replacement gadget. \node[vertex] (u) at (1.2,3.0) {$u$}; \node[vertex] (v) at (3.6,3.0) {$v$}; \draw[edge] (u) -- node[above, pos=0.50, yshift=4mm] {core edge $(u,v)$} (v); % Replacement gadget. \node[vertex] (u0) at (0,0) {$(u,0)$}; \node[hub] (h) at (2.4,0) {$h_{uv}$}; \node[vertex] (v0) at (4.8,0) {$(v,0)$}; \node[leaf] (u1) at (0,-1.55) {$(u,1)$}; \node[leaf] (v1) at (4.8,-1.55) {$(v,1)$}; \draw[edge] (u0) -- node[above] {$1$} (h); \draw[edge] (h) -- node[above] {$1$} (v0); \draw[edge] (u0) -- (u1); \draw[edge] (v0) -- (v1); \node[above=3mm of u0] {$w=1$}; \node[above=3mm of v0] {$w=1$}; \node[above=3mm of h] {$w=P=N+1$}; \node[below=3mm of u1] {$w=0$}; \node[below=3mm of v1] {$w=0$}; % The arrow stops above the weight labels, so it does not overlap text. \draw[-Latex, thick] ($(u)!0.5!(v)+(0,-6mm)$) -- node[right, xshift=2mm] {becomes} ($(h.north)+(0,9mm)$); \end{tikzpicture} \caption{Local weighted-MIDS gadget for a core edge $(u,v)$. Selecting $(u,0)$ or $(v,0)$ corresponds to paying for a vertex-cover endpoint, while selecting the heavy hub $h_{uv}$ incurs penalty $P=N+1$.} \label{fig:mids-gadget} \end{figure} \paragraph{Oriented-incidence cycles: $c_8$.} $\textsc{BipartitePlanarCover}$ ($c_8$) processes the vertices in a fixed order. When $u$ is processed, each edge $\{u,v_j\}$ to a not-yet-processed neighbour, $j=1,\dots,d$, creates two \emph{oriented-incidence} nodes $x_{uv_j}$ and $x_{v_ju}$, of weights $1/\deg u$ and $1/\deg v_j$, joined by a \emph{forcing edge}, and consecutive incidences are joined by \emph{local edges} that close an even cycle $C_{2d}$ when $d\ge2$ (Figure~\ref{fig:bip-gadget}). Every edge of $G$ is handled once, from its first processed endpoint, so the auxiliary graph is a vertex-disjoint union of even cycles and single edges with $2m$ nodes: it is bipartite and planar, and a minimum-weight vertex cover of it is computed exactly by a dynamic program along each cycle, with no flow computation. A cover of the auxiliary graph contains an endpoint of every forcing edge and is decoded to $\{u:x_{uv}\text{ selected}\}$, a cover of $G$. The \emph{residual variant} always processes a vertex of minimum residual degree $d$ and weighs the gadget by residual degrees; its neighbour side then weighs $\sum_j1/d_{\mathrm{res}}(v_j)\le1$, so the exact cycle solve selects the neighbours, and the decoded cover is the complement of a greedy minimum-degree maximal independent set. Candidate $c_8$ keeps the better of the input-order and the residual variant. \begin{figure}[!htbp] \centering \begin{tikzpicture}[ auxL/.style={circle,draw=blue!70!black,fill=blue!12,minimum size=9mm,inner sep=1pt,font=\scriptsize}, auxR/.style={circle,draw=orange!80!black,fill=orange!18,minimum size=9mm,inner sep=1pt,font=\scriptsize}, force/.style={line width=1.1pt}, local/.style={line width=.7pt,dashed,draw=gray!70} ] \node[auxL] (a1) at (0,1.2) {$x_{uv_1}$}; \node[auxR] (b1) at (2.2,1.2) {$x_{v_1u}$}; \node[auxL] (a2) at (4.4,1.2) {$x_{uv_2}$}; \node[auxR] (b2) at (4.4,-0.6) {$x_{v_2u}$}; \node[auxL] (a3) at (2.2,-0.6) {$x_{uv_3}$}; \node[auxR] (b3) at (0,-0.6) {$x_{v_3u}$}; \draw[force] (a1) -- (b1); \draw[force] (a2) -- (b2); \draw[force] (a3) -- (b3); \draw[local] (b1) -- (a2); \draw[local] (b2) -- (a3); \draw[local] (b3) -- (a1); \end{tikzpicture} \caption{Oriented-incidence gadget of a vertex $u$ with $d=3$ unprocessed neighbours: an even cycle $C_6$. Solid forcing edges $\{x_{uv_j},x_{v_ju}\}$ encode the original edges $\{u,v_j\}$; dashed local edges close the cycle. Blue nodes (weight $1/\deg u$) decode to $u$, orange nodes (weight $1/\deg v_j$) to $v_j$.} \label{fig:bip-gadget} \end{figure} \paragraph{Bipartite layers: $c_9$.} $\textsc{BipartiteLayersCover}$ ($c_9$) treats every connected component on its own (Algorithm~\ref{alg:c9}). On a bipartite graph it uses a near-optimal linear-time bipartite solver, \textsc{BipartiteCover}: the maximal matching of \texttt{min\_maximal\_matching}, enlarged by at most $p=8$ phases of the Hopcroft--Karp algorithm~\cite{hopcroft1973algorithm}, each of which finds a maximal set of vertex-disjoint shortest augmenting paths in $O(n+m)$, and K\H{o}nig's construction~\cite{konig1931graphen}: with $Z$ the vertices reachable from the unmatched vertices of one side $T$ by alternating paths, the set $(T\setminus Z)\cup(Z\setminus T)$ is returned, the smaller of the two choices of $T$. A non-bipartite component is split into \emph{bipartite layers}. A breadth-first $2$-colouring gives each vertex the colour that disagrees with most of its coloured neighbours, ties against its parent, so that at least half of the edges join different colours; these edges form layer $0$, and their endpoints receive the copy index $0$. The remaining edges, without the vertices they leave isolated, are coloured in the same way and form layer $1$, with copy index $1$, and so on until no edge is left (Figure~\ref{fig:layers}). Every edge lies in exactly one layer. The layers are then solved in an order: in each layer the copies of the vertices selected in an earlier layer of the same order are discarded, together with their edges, which are covered, and the rest of the layer is solved by \textsc{BipartiteCover}. Different orders give different covers; all orders are tried when there are at most $q=6$ of them, and otherwise $q$ orders (the natural order, the reverse order and their rotations), and the smallest cover is kept. \begin{algorithm}[!htbp] \caption{\textsc{BipartiteLayersCover}$(\mathit{adj})$ --- strategy $c_9$} \label{alg:c9} \begin{algorithmic}[1] \Require Adjacency map of a graph without self-loops; limits $p=8$ (phases) and $q=6$ (orders) \Ensure A vertex cover $C$ \State $C\gets\emptyset$ \For{each connected component $K$} \State $R\gets E(K)$; $t\gets0$ \While{$R\neq\emptyset$} \State $\chi\gets$ breadth-first majority $2$-colouring of $(V(R),R)$ \State $B_t\gets\{uv\in R:\chi(u)\neq\chi(v)\}$ \Comment{layer $t$, copies $(u,t)$; $|B_t|\ge|R|/2$} \State $R\gets R\setminus B_t$; $t\gets t+1$ \EndWhile \State $\mathcal{O}\gets$ all orders of $B_0,\dots,B_{t-1}$ if $t!\le q$, else $q$ rotations of the natural and the reverse order \For{each order $(B_{\sigma(1)},\dots,B_{\sigma(t)})\in\mathcal{O}$} \State $S\gets\emptyset$ \For{$s=1,\dots,t$} $S\gets S\cup\textsc{BipartiteCover}(\{uv\in B_{\sigma(s)}:u\notin S,\ v\notin S\},p)$ \EndFor \EndFor \State $C\gets C\cup$ the smallest $S$ \EndFor \State \Return $C$ \end{algorithmic} \end{algorithm} \begin{figure}[!htbp] \centering \begin{tikzpicture}[ v/.style={circle,draw,thick,minimum size=7mm,inner sep=0pt,font=\small}, l0/.style={thick,blue!70!black}, l1/.style={line width=1.6pt,red!70!black,dashed}, lbl/.style={font=\small}] \begin{scope} \node[v] (a) at (90:1.5) {$a$}; \node[v,fill=gray!25] (b) at (18:1.5) {$b$}; \node[v] (c) at (-54:1.5) {$c$}; \node[v] (d) at (-126:1.5) {$d$}; \node[v,fill=gray!25] (e) at (162:1.5) {$e$}; \draw[l0] (a)--(b) (b)--(c) (d)--(e) (e)--(a); \draw[l1] (c)--(d); \node[lbl,align=center] at (0,-2.4) {(a) majority colouring of $C_5$ from $a$:\\ grey $=1$, white $=0$}; \end{scope} \begin{scope}[shift={(5.6,0)}] \node[v] (c0) at (-1.6,0.9) {$c$}; \node[v,fill=gray!25] (b0) at (-0.8,0.9) {$b$}; \node[v] (a0) at (0,0.9) {$a$}; \node[v,fill=gray!25] (e0) at (0.8,0.9) {$e$}; \node[v] (d0) at (1.6,0.9) {$d$}; \draw[l0] (c0)--(b0)--(a0)--(e0)--(d0); \node[lbl] at (2.9,0.9) {layer $0$}; \node[v] (c1) at (-0.4,-0.6) {$c$}; \node[v] (d1) at (0.4,-0.6) {$d$}; \draw[l1] (c1)--(d1); \node[lbl] at (2.9,-0.6) {layer $1$}; \node[lbl,align=center] at (0.6,-2.0) {(b) order $(0,1)$: layer $0$ gives $\{b,e\}$,\\ layer $1$ adds $c$ or $d$: $3=\tau(C_5)$}; \end{scope} \end{tikzpicture} \caption{Strategy $c_9$ on the odd cycle $C_5$. (a) The breadth-first majority colouring from $a$ puts four of the five edges between the colours (solid): they form the bipartite layer $0$, a path. The edge $cd$ joins two vertices of colour $0$ and forms layer $1$ (dashed), with the copies $(c,1)$ and $(d,1)$. (b) Solving layer $0$ exactly gives $\{b,e\}$; in layer $1$ neither $c$ nor $d$ is selected yet, and one of them is added. The cover has $3=\tau(C_5)$ vertices.} \label{fig:layers} \end{figure} \paragraph{Labelled, weighted edge dominating set: $c_{10}$.} Candidate $c_{10}$ reduces every bipartite component to an edge dominating set problem on a gadget $D$. Every edge $\{u,v\}$ of $G$ becomes an \emph{edge-node} $(u,v)$, and a vertex $u$ with neighbours $n_0,\dots,n_{d-1}$ receives \emph{incidence nodes} $(u,0),\dots,(u,d-2)$ that thread its edge-nodes into a path $(u,n_0)-(u,0)-(u,n_1)-\cdots-(u,n_{d-1})$, whose edges are the \emph{path edges} of $u$; a chosen path edge of $u$ decodes to $u$ (Figure~\ref{fig:eds-gadget}). Every vertex carries a cover label shared along its path, choosing some but not all path edges of a vertex costs a prohibitive penalty, the path edges of every vertex weigh $K^\star$ in total, where $K^\star$ exceeds the number of edges, and every edge-node whose two endpoints are labelled $1$ costs one unit of overlap. A penalty-free solution is then the set of path edges of a set $C$ of vertices labelled $1$; it is an edge dominating set exactly when $C$ is a vertex cover, and it costs $K^\star|C|+e(C)$, with $e(C)$ the number of edges inside $C$. Its minimum is therefore a minimum vertex cover with the fewest doubly covered edges. The problem is solved by bucket elimination along a greedy minimum-degree order of $D$, eliminating a node only while its fill degree is at most $5$, so that no bag has more than six nodes, and within a table budget of $1024$ times the gadget size; the nodes that are not eliminated form a \emph{core}, fixed as in the best of $c_1,\dots,c_9$. With an empty core $c_{10}$ is a minimum cover of the component. Minimum edge dominating set is NP-hard even on bipartite graphs of maximum degree $3$~\cite{yannakakis1980edge}, so the core is what keeps $c_{10}$ linear. \begin{figure}[!htbp] \centering \begin{tikzpicture}[ vtx/.style={circle,draw,thick,minimum size=7mm,inner sep=0pt,font=\small}, enode/.style={rectangle,draw,thick,fill=gray!12,minimum width=10mm,minimum height=6mm,inner sep=1pt,font=\scriptsize}, inode/.style={circle,draw,thick,minimum size=8.5mm,inner sep=0pt,font=\scriptsize}, gedge/.style={thin,gray!70!black}, chosen/.style={line width=2.2pt,red!75!black}, lbl/.style={font=\scriptsize,fill=white,inner sep=1pt}] % ---------------- Left: the graph G ---------------- \begin{scope}[shift={(0,0)}] \node[vtx,fill=red!15] (u) at (0,0) {$u$}; \node[vtx] (v) at (-1.3,1.3) {$v$}; \node[vtx] (w) at (1.4,1.3) {$w$}; \node[vtx,fill=red!15] (z) at (1.4,-1.3) {$z$}; \draw[thick] (u)--(v) (u)--(w) (u)--(z) (w)--(z); \node[font=\small] at (0,-2.6) {$G$, $\tau(G)=2$}; \end{scope} \draw[-{Stealth[length=3mm]},thick] (2.6,0) -- (3.6,0) node[midway,above,font=\scriptsize]{gadget $D$}; % ---------------- Right: the gadget D ---------------- \begin{scope}[shift={(4.6,0)}] % edge-nodes \node[enode] (euv) at (0,0) {$(u,v)$}; \node[enode] (euw) at (2.2,0) {$(u,w)$}; \node[enode] (euz) at (4.4,0) {$(u,z)$}; \node[enode] (ewz) at (6.6,0) {$(w,z)$}; % incidence nodes of u (path of u above) \node[inode,fill=red!10] (u0) at (1.1,1.7) {$(u,0)$}; \node[inode,fill=red!10] (u1) at (3.3,1.7) {$(u,1)$}; % incidence nodes of z (above) and of v, w (below) \node[inode] (v0) at (0,-1.8) {$(v,0)$}; \node[inode] (w0) at (4.4,-1.8) {$(w,0)$}; \node[inode,fill=red!10] (z0) at (5.5,1.7) {$(z,0)$}; % gadget edges \draw[gedge] (u0)--(euw) (u1)--(euw); \draw[gedge] (v0)--(euv); \draw[gedge] (w0)--(euw) (w0)--(ewz); \draw[gedge] (z0)--(euz); % chosen edges: all path edges of the vertices labelled 1 (u and z) \draw[chosen] (u0)--(euv) (u0)--(euw); \draw[chosen] (u1)--(euw) (u1)--(euz); \draw[chosen] (z0)--(euz) (z0)--(ewz); \node[lbl,text=red!75!black] at (0.25,1.05) {$\to u$}; \node[lbl,text=red!75!black] at (4.15,1.05) {$\to u$}; \node[lbl,text=red!75!black] at (6.45,1.05) {$\to z$}; \end{scope} \end{tikzpicture} \caption{The edge-dominating-set gadget of $c_{10}$. Left: a graph $G$ in which $u$ has neighbours $v,w,z$ (adjacency order) and $w,z$ are adjacent. Right: its gadget $D$. Every edge of $G$ is an edge-node (grey box); every vertex receives incidence nodes (circles) that thread its edge-nodes into a path, e.g.\ $(u,v)-(u,0)-(u,w)-(u,1)-(u,z)$ for $u$, while $v$, of degree $1$, has the single node $(v,0)$. The incidence index $k$ in $(u,k)$ is a position on the path of $u$, never a neighbour. The thick red edges are all the path edges of the vertices labelled $1$, $u$ and $z$ (shaded): they form an edge dominating set of $D$, since every gadget edge shares an endpoint with one of them, and they decode to the cover $\{u,z\}$. Its weight is $2K^\star+1$: one unit $K^\star$ per vertex, and an overlap of $1$ because the edge $uz$ has both endpoints in the cover. Every minimum cover of $G$ ($\{u,z\}$ or $\{u,w\}$) has this weight, and no other labelling is lighter.} \label{fig:eds-gadget} \end{figure} \paragraph{Weighted subdivision reduction: $c_{11}$.} The \emph{subdivision graph} $S(G)$ has a \emph{vertex-node} $(u,u)$ for every vertex and an \emph{edge-node} $(u,w)$ for every edge, joined to $(u,u)$ and $(w,w)$; it is bipartite, with $n+m$ nodes and $2m$ edges. A set $X$ of vertices \emph{dominates} the edge-node $(u,w)$ when $u\in X$ or $w\in X$; with vertex-nodes of weight $1$ and an undominated edge-node costing $n+1$, a minimum-weight selection dominates every edge-node and is a minimum vertex cover (Lemma~\ref{lem:phi}). A vertex cover of $S(G)$ itself would not encode the problem: it may take the edge-node instead of either endpoint, so on a forest its minimum is the set of edge-nodes, which decodes to the empty set; $c_{11}$ keeps the domination constraint, which carries the hardness, and uses the bipartite structure for bookkeeping. $\textsc{SubdivisionCover}$ ($c_{11}$) keeps a residual graph of undecided vertices and undominated edges and applies four exact rules: (R0) a vertex of residual degree $0$ is left out; (R1) the neighbour of a vertex of residual degree $1$ is selected; (R2) the two neighbours of a vertex of residual degree $2$ are selected when they are adjacent; and (R3) a vertex $u$ of residual degree $2$ with non-adjacent neighbours $a,b$ is folded with them into one vertex $z$ adjacent to $(N(a)\cup N(b))\setminus\{u\}$, as in the folding rule of Chen, Kanj and Jia~\cite{chen2001vertex}, and unfolded at the end into $\{a,b\}$ if $z$ was selected and into $u$ otherwise. Folding is charged to a work budget of $4(n+m)$. When no rule applies a vertex of largest residual degree is \emph{peeled} into the cover, either among all vertices (\texttt{max}) or among the vertices of the best of $c_1,\dots,c_{10}$ (\texttt{ref}), following the reducing-peeling scheme of Chang, Li and Zhang~\cite{chang2017computing}. The ensemble keeps the smaller of the two variants, both with folding. Figure~\ref{fig:subdivision} shows the reduction on a small graph. \begin{Lemma}[Domination encodes vertex cover] \label{lem:phi} A set $X\subseteq V$ dominates every edge-node of $S(G)$ if and only if $X$ is a vertex cover of $G$. Every minimiser of $\Phi(X)=|X|+(n+1)\cdot|\{(u,w):u\notin X,\,w\notin X\}|$ is a minimum vertex cover, and $\min_X\Phi(X)=\tau(G)$. \end{Lemma} \begin{proof} The edge-node $(u,w)$ is dominated exactly when $X$ covers $\{u,w\}$, so a cover pays no penalty and $\Phi(X)=|X|$. A set that leaves an edge-node undominated has $\Phi(X)\ge n+1>n\ge\Phi(V)$, so a minimiser is a cover of minimum size. \end{proof} \begin{figure}[!htbp] \centering \begin{tikzpicture}[ vtx/.style={circle,draw,thick,minimum size=7mm,inner sep=0pt,font=\small}, vnode/.style={circle,draw,thick,minimum size=8mm,inner sep=0pt,font=\scriptsize}, enode/.style={rectangle,draw,thick,fill=gray!12,minimum width=9mm,minimum height=6mm,inner sep=1pt,font=\scriptsize}, sel/.style={fill=red!18}, half/.style={thin,gray!60!black}, dom/.style={line width=1.6pt,red!70!black}, note/.style={font=\scriptsize,align=left}] % ---------------- (a) the graph G ---------------- \begin{scope}[shift={(0,0)}] \node[vtx,sel] (a) at (-0.7,1.3) {$a$}; \node[vtx,sel] (b) at (0.7,1.3) {$b$}; \node[vtx] (c) at (0,0.2) {$c$}; \node[vtx,sel] (d) at (0,-1.0) {$d$}; \node[vtx] (e) at (0,-2.2) {$e$}; \draw[thick] (a)--(b) (b)--(c) (c)--(a) (c)--(d) (d)--(e); \node[font=\small] at (0,-3.1) {(a) $G$, $\tau(G)=3$}; \end{scope} \draw[-{Stealth[length=3mm]},thick] (1.4,-0.4) -- (2.3,-0.4) node[midway,above,font=\scriptsize]{$S(G)$}; % ---------------- (b) the subdivision S(G) ---------------- \begin{scope}[shift={(3.0,0)}] \node[vnode,sel] (sa) at (0,1.1) {$(a,a)$}; \node[vnode,sel] (sb) at (1.5,1.1) {$(b,b)$}; \node[vnode] (sc) at (3.0,1.1) {$(c,c)$}; \node[vnode,sel] (sd) at (4.5,1.1) {$(d,d)$}; \node[vnode] (se) at (6.0,1.1) {$(e,e)$}; \node[enode] (eab) at (0.0,-1.2) {$(a,b)$}; \node[enode] (eca) at (1.5,-1.2) {$(c,a)$}; \node[enode] (ebc) at (3.0,-1.2) {$(b,c)$}; \node[enode] (ecd) at (4.5,-1.2) {$(c,d)$}; \node[enode] (ede) at (6.0,-1.2) {$(d,e)$}; \draw[half] (sb)--(eab) (sc)--(eca) (sc)--(ebc) (sc)--(ecd) (se)--(ede); \draw[dom] (sa)--(eab) (sa)--(eca) (sb)--(ebc) (sd)--(ecd) (sd)--(ede); \node[note] at (3.0,-2.35) {(R1) $e$ has one open edge-node: select $d$, leave $e$ out;\\(R2) then $c$ has two open edge-nodes, to adjacent $a,b$: select $a,b$, leave $c$ out.}; \node[font=\small] at (3.0,-3.1) {(b) $S(G)$: the selection $\{a,b,d\}$ dominates every edge-node}; \end{scope} % ---------------- (c) a fold ---------------- \begin{scope}[shift={(0.6,-5.2)}] \node[vtx] (fa) at (-1.0,0) {$a$}; \node[vtx] (fu) at (0,0.9) {$u$}; \node[vtx] (fb) at (1.0,0) {$b$}; \node[vtx] (fx) at (-1.6,-1.1) {$x$}; \node[vtx] (fy) at (0,-1.1) {$y$}; \node[vtx] (fz) at (1.6,-1.1) {$v$}; \draw[thick] (fu)--(fa) (fu)--(fb) (fa)--(fx) (fa)--(fy) (fb)--(fy) (fb)--(fz); \draw[-{Stealth[length=3mm]},thick] (2.4,-0.2) -- (3.4,-0.2) node[midway,above,font=\scriptsize]{(R3)}; \node[vtx,fill=blue!10] (z) at (5.0,0.5) {$z$}; \node[vtx] (gx) at (4.0,-1.1) {$x$}; \node[vtx] (gy) at (5.0,-1.1) {$y$}; \node[vtx] (gz) at (6.0,-1.1) {$v$}; \draw[thick] (z)--(gx) (z)--(gy) (z)--(gz); \node[note] at (9.0,-0.2) {$\tau(G)=\tau(G')+1$;\\ $z$ selected $\Rightarrow$ cover $\{a,b\}$,\\ $z$ left out $\Rightarrow$ cover $\{u\}$.}; \node[font=\small] at (3.0,-2.0) {(c) folding a vertex $u$ of degree $2$ with non-adjacent neighbours $a,b$}; \end{scope} \end{tikzpicture} \caption{The weighted subdivision reduction of $c_{11}$. (a) A graph $G$ with a triangle $abc$ and a pendant path $c\,d\,e$. (b) Its subdivision $S(G)$: vertex-nodes (circles) keep the vertices, every edge becomes an edge-node (grey box) joined to its two endpoints, so $S(G)$ is bipartite. The reductions select $d$ by (R1) and then $a,b$ by (R2); the selected vertex-nodes (shaded) dominate every edge-node through the thick edges, and no peel was needed, so $\{a,b,d\}$ is a minimum vertex cover (Theorem~\ref{thm:c11}). (c) The fold (R3): $u,a,b$ become one vertex $z$ adjacent to $N(a)\cup N(b)\setminus\{u\}$, and the optimum drops by exactly one.} \label{fig:subdivision} \end{figure} \paragraph{Bounded-treewidth dynamic program: $c_{12}$.} $\textsc{TreewidthDPCover}$ ($c_{12}$) solves vertex cover exactly by bucket elimination along a greedy minimum-degree order, eliminating a vertex only while its degree in the fill graph is at most $10$ and the total table size stays within $256(n+m)$; the remaining vertices form a core, fixed as in the best of $c_1,\dots,c_{11}$. \subsection{Improvers} \label{sec:improvers} \paragraph{Union and local search: $c_{13}$ and $c_{14}$.} Candidate $c_{13}$ prunes the union of $c_2,\dots,c_8$, the pruning pass of Hvala applied to all the independent heuristics at once. $\textsc{LocalSearchCover}$ ($c_{14}$) improves the complementary independent set $S=V\setminus C$ of the best of $c_1,\dots,c_{13}$. For $v\notin S$ let $\mathrm{tight}(v)=|N(v)\cap S|$. A $(1,2)$-swap of Andrade, Resende and Werneck~\cite{andrade2012fast} removes a vertex $x\in S$ and inserts two non-adjacent neighbours of $x$ with tightness $1$, enlarging $S$ by one; an iterated local search step forces a vertex into $S$, evicts its neighbours, reinserts freed vertices and is undone if $S$ shrank. Every adjacency scan is charged to a work counter, and the search stops after $b(n+m)$ work with $b=100$. \paragraph{Reduce-and-search and consensus: $c_{15}$ and $c_{16}$.} The swap search of $c_{14}$ stops on plateaus, and the reductions of $c_{11}$ stop when every residual degree is at least $3$. $\textsc{ReduceSearchCover}$ ($c_{15}$) alternates the two for three rounds from the best of $c_1,\dots,c_{14}$: a swap search with a different fixed seed in each round, which also accepts a cover of equal size and so moves along the plateau, and a pass of $c_{11}$ guided by the searched cover, whose exact rules correct it wherever a vertex of residual degree at most $2$ appears; a cover is accepted whenever it is not larger. $\textsc{ConsensusForceCover}$ ($c_{16}$) turns the agreement of the earlier covers into a reduction. A vertex can be forced into every cover by a self-loop on it; $c_{16}$ obtains the same effect by deleting the forced vertices and adding them to the cover. In at most three rounds it forces the vertices contained in all, then $90\%$, then $75\%$ of the covers of its pool, which starts with $c_1,\dots,c_{15}$ and receives the cover of every round, solves the residual graph again with the best of the pruned maximal-matching cover, $c_5$ and $c_{11}$ (\texttt{max} with folding), and prunes the union on $G$ (Figure~\ref{fig:consensus}). It stops early when its best cover equals a certified matching lower bound $L$, the larger of $|M|$ and a Karp--Sipser matching~\cite{karp1981maximum}, or when a round would force the same set as the previous one. \begin{figure}[!htbp] \centering \begin{tikzpicture}[ vtx/.style={circle,draw,thick,minimum size=7mm,inner sep=0pt,font=\small}, forced/.style={fill=red!25}, res/.style={fill=blue!10}, note/.style={font=\scriptsize,align=center,text width=5.2cm}] \begin{scope} \node[vtx,forced] (h) at (0,0) {$h$}; \node[vtx] (a) at (-1.3,1.0) {$a$}; \node[vtx] (b) at (0,1.5) {$b$}; \node[vtx] (c) at (1.3,1.0) {$c$}; \node[vtx] (x) at (-1.3,-1.0) {$x$}; \node[vtx] (y) at (1.3,-1.0) {$y$}; \node[vtx] (z) at (0,-2.0) {$z$}; \draw[thick] (h)--(a) (h)--(b) (h)--(c) (h)--(x) (h)--(y) (a)--(b) (x)--(z) (y)--(z) (x)--(y); \node[note,anchor=north] at (0,-2.5) {(a) $h$ lies in every cover of the pool:\\ votes $13/13$, forced in round $1$}; \end{scope} \draw[-{Stealth[length=3mm]},thick] (2.4,-0.3) -- (4.2,-0.3) node[midway,above,font=\scriptsize]{delete $h$}; \begin{scope}[shift={(6.6,0)}] \node[vtx] (a2) at (-1.3,1.0) {$a$}; \node[vtx,res] (b2) at (0,1.5) {$b$}; \node[vtx] (c2) at (1.3,1.0) {$c$}; \node[vtx,res] (x2) at (-1.3,-1.0) {$x$}; \node[vtx,res] (y2) at (1.3,-1.0) {$y$}; \node[vtx] (z2) at (0,-2.0) {$z$}; \draw[thick] (a2)--(b2) (x2)--(z2) (y2)--(z2) (x2)--(y2); \node[note,anchor=north] at (0,-2.5) {(b) residual graph $G-h$: an edge, a triangle and the isolated $c$;\\ the residual solver returns $\{b,x,y\}$, which is optimal}; \end{scope} \node[note,text width=9cm,anchor=north] at (3.3,-4.45) {(c) $c_{16}=\textsc{Prune}(\{h\}\cup\{b,x,y\})=\{h,b,x,y\}$, and $\tau(G)=4$.}; \end{tikzpicture} \caption{One round of consensus forcing ($c_{16}$). (a) The vertex $h$ is in every cover of the pool, so it is forced: it is deleted and added to the cover, as a self-loop on $h$ would require. (b) The residual graph splits into small components, on which the linear-time solvers are exact. (c) The union is pruned on $G$. Forcing helps when the strategies agree on the vertices of an optimal cover and disagree elsewhere: the residual graph then carries only the undecided part of the instance.} \label{fig:consensus} \end{figure} \paragraph{Swap-maximize refinement: $c_{17}$.} $\textsc{RefineCover}$ ($c_{17}$) refines every candidate. For a cover $C$ with complementary independent set $I$, and for every $u\in C\cup\{v_{\max}\}$, with $v_{\max}$ a vertex of maximum degree, it moves $u$ into the independent set, evicts the neighbours of $u$ from it, regrows a maximal independent set by scanning the cover vertices adjacent to an evicted vertex in ascending order of degree, and keeps the complement when it is strictly smaller than the best cover found so far. A move may evict many vertices at once, which the $(1,2)$-swaps cannot do, and it succeeds when the low-degree vertices it frees outnumber the evicted ones. The moves stop after $100(n+m)$ work per candidate, sorting included. \section{Correctness of the Algorithm} \label{sec:correctness} \begin{Theorem} \label{thm:correctness} Algorithm~\ref{alg:main} always returns a vertex cover of the input graph $G$. \end{Theorem} \begin{proof} Isolated vertices and self-loops need no cover, so it suffices that every candidate $c_1,\dots,c_{16}$ is a cover of the cleaned graph and that the refinement preserves this, since $c_{17}$ is one of the refined candidates. Pruning preserves validity: a vertex is removed only when all its neighbours are in the set, so its edges stay covered. Candidate $c_1$ is completed by a greedy cover of the edges that its decoded set leaves uncovered, and then pruned. Candidate $c_2$ consists of both endpoints of a maximal matching, and an edge with no matched endpoint would extend the matching. Candidates $c_3$ and $c_5$ add vertices until no active vertex has positive degree, and every deletion removes only covered edges. In $c_4$ every original edge is an auxiliary edge, and when its first scanned endpoint is processed it is either already covered or one of its endpoints is selected. Candidate $c_6$ adds an endpoint of every edge whose slack is exhausted, which the local-ratio scan guarantees for every edge~\cite{barYehudaEven1985}. Candidate $c_7$ ends with a repair scan that adds an endpoint of every uncovered edge. In $c_8$ every edge of $G$ is a forcing edge of the auxiliary graph, whose cover is exact, so an endpoint is decoded. Candidate $c_9$ is a cover by Proposition~\ref{prop:c9}(i). Candidate $c_{10}$ keeps only penalty-free dynamic-programming states, which decode to covers, and takes the earlier best cover on non-bipartite components. Candidate $c_{11}$ stops only when the residual graph has no edge, an edge leaves it only when an endpoint is selected, and unfolding a fold vertex $z$ adds $\{a,b\}$ if $z$ was selected and $u$ otherwise, which covers every edge at $u$, $a$ and $b$. In $c_{12}$ the dynamic program covers every edge between eliminated vertices and every edge to the core, and the core is fixed as in a cover. A union of covers is a cover, which handles $c_{13}$. Candidates $c_{14}$, the search step of $c_{15}$ and every refinement are complements of independent sets, hence covers, and a reduction pass of $c_{15}$ is accepted only after it is checked to be a cover. In $c_{16}$ a round returns $S\cup C'$ with $C'$ a cover of $G-S$, so every edge with an endpoint in $S$ is covered by $S$ and every other edge by $C'$. \end{proof} \section{Approximation Ratio} \label{sec:approx} \subsection{Ratio $2$ and the bound $2\tau-r$} \label{sec:twotau} \begin{Theorem}[Every pruned candidate is minimal] \label{thm:minimal} Every output of Algorithm~\ref{alg:prune} is a minimal vertex cover. In particular $c_1,\dots,c_{13}$ are minimal covers. \end{Theorem} \begin{proof} A vertex $v$ that survives its test has a neighbour outside the current set, and later removals only enlarge the outside, so after the pass every remaining vertex has a neighbour outside the cover; that is, no vertex can be removed. \end{proof} \begin{Theorem}[Unconditional ratio $2$] \label{thm:ratio2} For every graph $G$, Algorithm~\ref{alg:main} returns a cover $C$ with $|C|\le2\tau(G)$. \end{Theorem} \begin{proof} Before pruning, $c_2$ consists of both endpoints of a maximal matching $M$; any cover contains an endpoint of each of the $|M|$ disjoint edges of $M$, so $\tau(G)\ge|M|$ and $|c_2|\le2|M|\le2\tau(G)$~\cite{papadimitriou1998combinatorial}. The returned cover is the smallest refined candidate, and a refinement never enlarges a cover, so $|C|\le|c_2|$. \end{proof} \begin{Theorem}[$2\tau-r$ on every graph] \label{thm:twotau} Let $r(G)$ be the number of connected components of $G$ that have an edge. The pruned candidate $c_2$, for every maximal matching, and therefore the cover $C$ returned by Algorithm~\ref{alg:main}, satisfy \[ |C|\ \le\ |c_2|\ \le\ 2\,\tau(G)-r(G),\qquad\text{so}\qquad\frac{|C|}{\tau(G)}\ \le\ 2-\frac{r(G)}{\tau(G)}. \] \end{Theorem} \begin{proof} Whether pruning removes a vertex depends only on its neighbours, and the restriction of a maximal matching to a component is a maximal matching of it, so it suffices to prove $|c_2|\le2\tau(G)-1$ for a connected graph $G$ with an edge and to sum over the components. Let $M$ be the maximal matching and $V(M)$ its matched vertices. Always $|c_2|\le|V(M)|=2|M|\le2\nu(G)\le2\tau(G)$; suppose for a contradiction that $|c_2|=2\tau(G)$. Then equality holds throughout: pruning removed nothing, so $c_2=V(M)$ is a minimal cover by Theorem~\ref{thm:minimal}, and $|M|=\nu(G)=\tau(G)$, so $M$ is a maximum matching. Take an edge $uv\in M$. By minimality $u$ has a neighbour $a\notin V(M)$ and $v$ has a neighbour $b\notin V(M)$. If $a\neq b$, then $a\,u\,v\,b$ is an $M$-augmenting path, which contradicts the maximality of $|M|$. Hence $u$ and $v$ have a single common neighbour $a_{uv}\notin V(M)$, and $u,v,a_{uv}$ form a triangle. Let $A=\{a_{uv}:uv\in M\}$ and, for $a\in A$, let $M_a$ be the edges $uv$ of $M$ with $a_{uv}=a$. A cover $K$ of $G$ contains at least $|M_a|+1$ vertices of $\{a\}\cup V(M_a)$: if $a\in K$, then $a$ and an endpoint of each edge of $M_a$; if $a\notin K$, both endpoints of every edge of $M_a$, since they are adjacent to $a$. These sets are disjoint for different $a$ and the sets $M_a$ partition $M$, so $\tau(G)\ge|M|+|A|\ge|M|+1>\tau(G)$, a contradiction. Hence $|c_2|\le2\tau(G)-1$, and $|C|\le|c_2|$ as in Theorem~\ref{thm:ratio2}. \end{proof} \begin{Corollary}[Ratio $1.999999999$ below $10^{9}$] \label{cor:billion} If $\tau(G)\le10^{9}\,r(G)$, then the cover $C$ returned by Algorithm~\ref{alg:main} satisfies $|C|\le1.999999999\,\tau(G)$. In particular this holds for every graph with at most $10^{9}+1$ vertices. \end{Corollary} \begin{proof} $2-r/\tau\le2-10^{-9}$ is equivalent to $\tau\le10^{9}r$. A component with $n_i\ge2$ vertices has $\tau_i\le n_i-1$, so if $n\le10^{9}+1$ then $\tau\le10^{9}\le10^{9}r$. \end{proof} Theorem~\ref{thm:twotau} is elementary, and the same bound holds for any algorithm that returns a pruned maximal-matching cover. It is not a $(2-\varepsilon)$-approximation: along any sequence of connected graphs with $\tau\to\infty$ the margin $1/\tau$ tends to $0$, as for the classical $2-\Theta(1/\sqrt{\log n})$ guarantees~\cite{karakostas2009better}, so it is consistent with every hardness result. It does settle a question that experiments cannot: every graph in any experiment we know of has far fewer than $10^{9}$ vertices, so on such graphs a ratio of at most $1.999999999$ is a theorem, not an empirical finding. \subsection{Per-class guarantees of the strategies} \label{sec:perclass} Because \textsc{Salvador} returns the smallest refined candidate, a guarantee proved for one candidate on a class of graphs holds for the returned cover on that class. Throughout, $R_0=1.999999999=2-\varepsilon_0$ with $\varepsilon_0=10^{-9}$, $\alpha(G)$ is the independence number, $\bar d$ the average degree, $\Delta$ the maximum degree and $W(G)=\sum_{uv\in E}1/\max\{\deg u,\deg v\}$. \begin{Lemma}[Safe vertices] \label{lem:safe} For every graph $G$ and vertex $w$, $\tau(G-w)\ge\tau(G)-1$, with equality if and only if $w$ belongs to some minimum vertex cover. If $v$ has degree $1$ and $w$ is its neighbour, then $w$ belongs to some minimum vertex cover. \end{Lemma} \begin{proof} A cover of $G-w$ plus $w$ covers $G$; a minimum cover of $G$ containing $w$, minus $w$, covers $G-w$; and conversely a minimum cover of $G-w$ plus $w$ is a minimum cover of $G$ when $\tau(G-w)=\tau(G)-1$. A minimum cover contains $v$ or $w$, and replacing $v$ by $w$ keeps it a cover, since $vw$ is the only edge at $v$. \end{proof} \begin{Lemma}[Exactness criterion for Min-to-Min] \label{lem:mtm-criterion} Every vertex added by $c_5$ is a neighbour of a vertex of minimum positive degree in the current active graph, and is then removed from it. Consequently, if every added vertex belongs to some minimum vertex cover of the current active graph, then $|c_5|=\tau(G)$. \end{Lemma} \begin{proof} Every vertex of positive current degree $k$ has an entry in the bucket $B_k$, since an entry is pushed whenever a degree changes, and stale entries are skipped. Removing a vertex lowers the degree of each neighbour by one, so all positive degrees stay at least the current minimum minus one, and the bucket pointer, decreased by at most one per step and advanced to the first non-empty bucket, always indexes the minimum positive degree. Let $w_1,\dots,w_k$ be the added vertices, $G_0=G$ and $G_i=G_{i-1}-w_i$; the last graph has no edge. If each $w_i$ lies in some minimum cover of $G_{i-1}$, Lemma~\ref{lem:safe} gives $\tau(G_i)=\tau(G_{i-1})-1$, so $|c_5|=k=\tau(G)$. \end{proof} \begin{Theorem}[Classes solved exactly by $c_5$] \label{thm:mtm-exact} If every component of $G$ is a tree, a path, a cycle, a complete graph or a complete bipartite graph, then $|c_5|=\tau(G)$, and \textsc{Salvador} returns a minimum vertex cover. \end{Theorem} \begin{proof} It suffices that each added vertex is safe in the component $K$ of the popped vertex $v$, which has minimum degree in $K$, and that deleting it leaves components of the listed types. In a tree or a path $v$ is a leaf, so its neighbour is safe by Lemma~\ref{lem:safe}, and deleting a vertex leaves trees or paths. A cycle $C_k$, a complete graph $K_n$ and a balanced $K_{a,a}$ are vertex-transitive, so every vertex lies in some minimum cover, and $C_k-w=P_{k-1}$, $K_n-w=K_{n-1}$, $K_{a,a}-w=K_{a-1,a}$. In $K_{a,b}$ with $a\deg l$ for every $r\in R_K$ and $l\in L_K$. Then $|c_5|=|c_8|=\tau(G)$, and \textsc{Salvador} returns a minimum vertex cover. \end{Theorem} \begin{proof} \emph{The optimum.} In case~(a) both sides have $|V(K)|/2$ vertices and $\tau(K)\ge|E(K)|/d_K=|V(K)|/2$, so each side is a minimum cover. In case~(b) let $a=\max_{L_K}\deg$ and $b=\min_{R_K}\deg>a$; for $S\subseteq R_K$ the edges between $S$ and $N(S)$ give $b|S|\le a|N(S)|$, so $|N(S)|>|S|$ for $S\ne\emptyset$, Hall's theorem~\cite{hall1935representatives} gives a matching saturating $R_K$, and $R_K$ is a minimum cover. So it suffices that each candidate contains at most one side of each component, the side $R_K$ in case~(b). \emph{Candidate $c_5$.} In case~(a) call $L_K$ the side of the first vertex of $K$ that $c_5$ pops. We show that every vertex popped in $K$ lies in $L_K$, so that every added vertex, a neighbour of it, lies in $R_K$. While this holds, no vertex of $L_K$ is removed, so every remaining vertex of $R_K$ keeps its original degree, while vertices of $L_K$ can only lose degree. A popped vertex has minimum positive degree $\delta$ (Lemma~\ref{lem:mtm-criterion}). Suppose a remaining $r\in R_K$ were popped. In case~(b) any neighbour $l$ of $r$ has positive degree at most $\deg l<\deg r=\delta$, a contradiction. In case~(a) $\delta=d_K$, so every vertex of $L_K$ has degree $0$ or $d_K$; a vertex of $L_K$ adjacent to $r$ has degree $d_K$ and hence all its neighbours remain, and every remaining vertex of $R_K$ keeps all its neighbours, so alternating between the sides from $r$ reaches all of $K$ through remaining vertices and no vertex of $R_K$ has been removed. But the first vertex popped in $K$ lies in $L_K$ and its added neighbour, in $R_K$, was removed. Hence $c_5\cap V(K)\subseteq R_K$ and $|c_5|\le\tau(G)$. \emph{Candidate $c_8$.} By the proof of Lemma~\ref{lem:carowei}, the residual variant processes a vertex $u$ of minimum positive residual degree, puts all its residual neighbours into the cover and deletes $u$ with them. With $L_K$ defined by the first processed vertex in case~(a), the argument for $c_5$, with residual degrees, shows that every processed vertex of $K$ lies in $L_K$; so every vertex put into the cover lies in $R_K$, and every vertex of $R_K$ is eventually put there. Pruning keeps a minimum cover. \end{proof} Case~(a) contains every regular bipartite graph: even cycles, hypercubes, crown graphs, balanced complete bipartite graphs, bipartite double covers $H\times K_2$ of regular graphs, and random regular bipartite graphs, which are expanders of linear treewidth. Case~(b) contains every unbalanced complete bipartite graph. Neither case needs a bound on the degree or on the treewidth, and neither depends on how ties are broken. \begin{Theorem}[Matching certificate] \label{thm:matching} For every graph with an edge, $|C|\le2\nu(G)$, so $|C|/\tau(G)\le2\nu(G)/\tau(G)$, and the ratio is at most $R_0$ whenever $\tau(G)\ge2\nu(G)/R_0$. \end{Theorem} \begin{proof} $|C|\le|c_2|\le2|M|\le2\nu(G)$. \end{proof} Since $\tau\le2\nu$ always holds, Theorem~\ref{thm:matching} leaves out exactly the \emph{nearly K\H{o}nig--Egerv\'ary} graphs, with $\nu\le\tau<2\nu/R_0$. On every other graph the matching candidate alone beats $R_0$. Every candidate is a minimal cover (Theorem~\ref{thm:minimal}), which gives a guarantee that does not depend on the strategy. \begin{Corollary}[Low independence ratio] \label{cor:lowalpha} If $\alpha(G)\le(1-1/R_0)\,n$, then every minimal cover, and in particular every candidate, has ratio at most $R_0$. More precisely: (a) if $V$ can be partitioned into cliques of size at least $k\ge3$, every minimal cover has ratio at most $k/(k-1)\le3/2$; (b) if $G$ is $d$-regular with smallest adjacency eigenvalue $\lambda_{\min}\ge-(1-\varepsilon_0)d$, every minimal cover has ratio at most $1+|\lambda_{\min}|/d\le R_0$, for every degree $d$. \end{Corollary} \begin{proof} A minimal cover has at most $n$ vertices and $\tau=n-\alpha\ge n/R_0$. For~(a), $\alpha$ is at most the number of cliques, at most $n/k$. For~(b), Hoffman's ratio bound~\cite{hoffman1970eigenvalues} gives $\alpha\le n|\lambda_{\min}|/(d+|\lambda_{\min}|)$, so $n/\tau\le1+|\lambda_{\min}|/d$. \end{proof} \begin{Theorem}[Max-degree greedy: $c_3$] \label{thm:greedy} For every graph of maximum degree $\Delta$, $|C|\le|c_3|\le H(\Delta)\,\tau(G)$, where $H(k)=\sum_{j=1}^{k}1/j$. In particular every graph of maximum degree at most $3$ gets ratio at most $H(3)=11/6$. \end{Theorem} \begin{proof} Vertex cover is the set cover instance whose elements are the edges and whose sets are the stars of the vertices, of size at most $\Delta$. The bucket queue processes degrees from the highest down and degrees only decrease, so every selected vertex has maximum current degree, and $c_3$ is the greedy set cover algorithm, whose ratio is at most $H(\Delta)$ by Johnson's theorem~\cite{johnson1974approximation}. Pruning only shrinks $c_3$. \end{proof} Theorem~\ref{thm:greedy} covers irregular and bipartite subcubic graphs, a class on which vertex cover is APX-hard~\cite{alimonti2000some}, which excludes an approximation scheme but not a fixed ratio such as $11/6$. \begin{Theorem}[Hallelujah bound: $c_4$] \label{thm:hallelujah} Let $S$ be the set produced by the weighted pass of the selection-aware Hallelujah resolution. For every graph with an edge, \[ |c_4|^2\ \le\ |S|^2\ \le\ W(G)\sum_{v\in S}\deg v\ \le\ 2m\,W(G)\ \le\ 2m\,\tau(G). \] Consequently the ratio is at most $R_0$ on every graph with $2mW(G)\le R_0^2\tau(G)^2$. \end{Theorem} \begin{proof} Candidate $c_4$ is the smaller of $S$ and an unweighted pass, so $|c_4|\le|S|$. Each vertex enters $S$ once, while an edge $\{u,w\}$ with no selected endpoint is inspected, and it is then an endpoint of minimum weight $1/\max\{\deg u,\deg w\}$ of that edge; the edge is covered afterwards, so distinct vertices of $S$ are charged to distinct edges and $\sum_{v\in S}1/\deg v\le W(G)$. This is the minimum weight of a cover of the auxiliary perfect matching, which is at most $\tau(G)$, because the $\deg v$ copies of each vertex of an optimal cover weigh $1$ in total. By the Cauchy--Schwarz inequality, $|S|^2\le(\sum_{v\in S}1/\deg v)(\sum_{v\in S}\deg v)\le W(G)\cdot2m$. \end{proof} \begin{Proposition}[Selection-aware Hallelujah on regular components] \label{prop:hall-regular} If every component $G_j$ of $G$ is $d_j$-regular with $n_j$ vertices, then before pruning $c_4$ is the complement of a maximal independent set, and $|c_4|\le\sum_jn_jd_j/(d_j+1)\le(2-2/(\max_jd_j+1))\,\tau(G)$. \end{Proposition} \begin{proof} Adjacent vertices have equal degree, so every weight comparison ties and the tie rule selects the still-unselected neighbours of each scanned unselected vertex $u$. Let $I$ be the vertices unselected when scanned: no vertex of $I$ is ever selected, since a later neighbour of it is already selected and is skipped, so $I$ is independent, and every selected vertex has a neighbour in $I$, so $I$ is maximal. In $G_j$ each vertex of $I$ dominates at most $d_j+1$ vertices, so $|I\cap V(G_j)|\ge n_j/(d_j+1)$; and $\tau(G_j)\ge n_j/2$. \end{proof} Theorem~\ref{thm:hallelujah} is strong when degrees are heterogeneous, and Proposition~\ref{prop:hall-regular} when they are equal; the published Hallelujah rule~\cite{vega2026hallelujah}, which resolves ties by labels, reaches $2-1/k$ on the even cycle $C_{2k}$, while the selection-aware rule returns $k$ vertices there. \begin{Proposition}[Edge-dominating-set gadget: $c_{10}$] \label{prop:c10} For every edge dominating set $F$ of the gadget $D$, the set of vertices that $F$ decodes to is a vertex cover; for every vertex cover $C$, the path edges of the vertices of $C$ form an edge dominating set that decodes to $C$. On a bipartite component $K$ the minimum cost of a labelled edge dominating set is $K^\star\tau(K)+\min\{e(C):C\text{ a minimum cover of }K\}$, so $c_{10}$ is a minimum cover of $K$, with the fewest doubly covered edges, whenever its core is empty, and no bag of its dynamic program has more than six nodes. \end{Proposition} \begin{proof} Let $\{u,v\}\in E$ and let $(u,k)$ be an incidence node joined to the edge-node $(u,v)$. The gadget edge between them is dominated by a chosen edge at $(u,k)$ or at $(u,v)$, and every gadget edge there lies on the path of $u$ or of $v$ and decodes to $u$ or $v$. Conversely, a gadget edge $\{(u,k),(u,x)\}$ is chosen if $u\in C$; otherwise $x\in C$ and a path edge of $x$ at $(u,x)$ dominates it. A solution that pays a penalty costs more than the penalty-free solution of all vertices, so every optimum is penalty-free, chooses the path edges of the set $C$ labelled $1$, is feasible exactly when $C$ is a cover, and costs $K^\star|C|+e(C)$ with $e(C)\le|E(K)|R_0\}$ be the \emph{residue}. Since $\beta\le2-r/\tau$, every graph of $\mathcal{R}$ has $\tau>10^{9}r$ and hence more than $10^9$ vertices; since $\beta\le2\nu/\tau$, every graph of $\mathcal{R}$ is nearly K\H{o}nig--Egerv\'ary. On $\mathcal{R}$ the right tool is a certificate that reads the returned cover. \begin{Lemma}[Slack identity] \label{lem:slack} Let $y:E\to[0,1]$ be a fractional matching, $|y|=\sum_ey_e$, $\mathrm{def}_y(v)=1-\sum_{e\ni v}y_e$, and for a set $C$ let $E(C)$ be the edges with both endpoints in $C$. Every vertex cover $C$ satisfies \[ |C|\ =\ |y|+\sigma_y(C),\qquad \sigma_y(C):=\sum_{e\in E(C)}y_e+\sum_{v\in C}\mathrm{def}_y(v)\ \ge\ 0, \] so the excess of $C$ over a minimum cover $C^*$ is $|C|-\tau(G)=\sigma_y(C)-\sigma_y(C^*)$. \end{Lemma} \begin{proof} Summing $1=\sum_{e\ni v}y_e+\mathrm{def}_y(v)$ over $v\in C$ gives $|C|=\sum_ey_e|e\cap C|+\sum_{v\in C}\mathrm{def}_y(v)$, and $|e\cap C|$ is $1$ or $2$, the latter exactly on $E(C)$, because $C$ is a cover. \end{proof} \begin{Theorem}[A-posteriori certificate] \label{thm:posterior} Let $\nu_f(G)$ be the optimum of the linear relaxation and $y$ a maximum fractional matching. For every graph and every cover $C$, \[ \frac{|C|}{\tau(G)}\ \le\ \frac{|C|}{\nu_f(G)}\ =\ 1+\frac{\sigma_y(C)}{\nu_f(G)}\ \le\ \frac{|C|}{\nu(G)}, \] and the three quantities on the right are computable in polynomial time. If $\tau(G)<2\nu(G)/R_0$, in particular on $\mathcal{R}$, then $|C|/\nu(G)<(1+5.1\cdot10^{-10})\,|C|/\tau(G)$; and if $\tau(G)=\nu(G)$, as on every bipartite graph, then $|C|-\tau(G)=\sigma_M(C)$ for every maximum matching $M$. \end{Theorem} \begin{proof} Weak duality gives $\nu\le\nu_f\le\tau$, and Lemma~\ref{lem:slack} with $|y|=\nu_f$ gives the equality; $\nu_f$ is half a maximum matching of the bipartite double cover. If $\tau<2\nu/R_0$, then $|C|/\nu<(2/R_0)|C|/\tau$ and $2/R_0<1+5.1\cdot10^{-10}$. If $\tau=\nu$, a maximum matching $M$ is an optimal $y$, so $\sigma_M(C^*)=0$. \end{proof} Theorem~\ref{thm:posterior} makes the ratio of every returned cover checkable on the residue up to a factor $1+5.1\cdot10^{-10}$, and exactly on bipartite graphs, but it is not a uniform bound, because it depends on $C$. By Lemma~\ref{lem:slack}, a ratio $R_0$ on a graph of $\mathcal{R}$ means $\sigma_y(C)\le R_0\tau-\nu_f$: the strategies must keep the violation of complementary slackness small. The minimum-degree rule of $c_5$ and $c_8$ never puts both endpoints of an edge into the cover when degrees are ordered across a bipartition (Theorem~\ref{thm:degsep}); the exact reductions of $c_{11}$ and $c_{15}$ never create slack (Theorem~\ref{thm:c11}); and a $(1,2)$-swap of $c_{14}$ or $c_{15}$ lowers $\sigma_y(C)$ by exactly one for every $y$. What is not proved is that together they keep $\sigma_y(C)$ below $R_0\tau-\nu_f$ on every graph of $\mathcal{R}$. If every fixed ratio below $2$ is NP-hard and $\mathrm{P}\ne\mathrm{NP}$, they cannot: \textsc{Salvador} then exceeds $R_0$ on infinitely many graphs, all in $\mathcal{R}$, and, since every minimal cover is within $1/(1-\delta)$ on graphs with $\alpha\le\delta n$, these graphs are YES-type instances of the Khot--Regev reduction, with an independent set of almost half the vertices, $\tau$ close to $\nu$, large treewidth, and degrees neither ordered across a bipartition nor heterogeneous enough for Theorem~\ref{thm:hallelujah}. \subsection{The split graph of $c_1$} \label{sec:splitlemmas} \begin{Lemma}[The component count] \label{lem:split} Let $M=(e_1,\dots,e_{|M|})$ be the maximal matching of $c_1$ and $F_k=\{e_1,\dots,e_k\}$. The projection $\pi$ maps the edges of the split graph bijectively onto the edges of $G$. After the first $k$ edges of $M$ are split, the split graph has $\mathrm{count}(k)=k+c(G-F_k)$ components with an edge. Moreover $\mathrm{count}(0)=r(G)$, $\mathrm{count}(|M|)\ge|M|$, and $\mathrm{count}(k+1)-\mathrm{count}(k)\in\{0,1,2\}$ for every $k$. \end{Lemma} \begin{proof} A split replaces each moved edge $(u,0)z$ by $(u,1)z$, so edges are neither created nor destroyed and their projections are unchanged; initially $\pi$ is a bijection. The edges of $M$ are disjoint, so after $F_k$ is split every vertex $u$ has at most one copy that carries edges not in $F_k$, namely $(u,1)$ if $u$ is an endpoint of $F_k$ and $(u,0)$ otherwise, and the edges of $F_k$ are isolated. Identifying each vertex with that copy maps the edges not in $F_k$ onto $G-F_k$ and preserves adjacency, which gives the formula. With $k=0$ it is $r(G)$, and with $k=|M|$ the $|M|$ isolated edges alone give $\mathrm{count}(|M|)\ge|M|$. Removing the edge $e_{k+1}$ from $G-F_k$ changes $c$ by $-1$ when $e_{k+1}$ forms a component by itself, by $+1$ when it is a bridge with an edge on both sides, and by $0$ otherwise, so $\mathrm{count}$ grows by $0$, $1$ or $2$. \end{proof} \begin{Lemma}[$|M|-1\le r'\le|M|$] \label{lem:rprime} Let $G$ have no isolated vertices and let $M$ be a maximal matching of $G$. Algorithm~\ref{alg:split} computes $\mathrm{count}(0),\dots,\mathrm{count}(|M|)$ correctly, and the split graph it returns has $r'$ components with an edge, where \[ r(G)\ \le\ r'\ \le\ |M|\ \le\ \nu(G)\ \le\ \tau(G)\ \le\ 2|M|\qquad\text{and}\qquad r'\ \ge\ |M|-1. \] Consequently $\tau(G)\le2\tau(G)-|M|\le\frac32\tau(G)$ and $2\tau(G)-|M|\le2\tau(G)-r'\le2\tau(G)-|M|+1$. \end{Lemma} \begin{proof} Every component of $G$ with an edge $xy$ contains an edge of $M$, because $x$ or $y$ is matched by maximality, so $r(G)\le|M|$; any matching is at most $\tau$, and $V(M)$ is a cover, so $|M|\le\nu\le\tau\le2|M|$. The union-find structure of Algorithm~\ref{alg:split} starts from $G-F_{|M|}$, and adding $e_{k+1}$ back joins two trees or none; the number of trees with an edge changes by $1-a$, with $a\in\{0,1,2\}$ the number of joined trees that already had an edge, or by $0$, which is exactly the change of $c(G-F_k)$. By Lemma~\ref{lem:split}, $\mathrm{count}$ starts at $r(G)\le|M|$, ends at a value of at least $|M|$, never decreases and grows by at most $2$ per step, so it takes a value in $\{|M|-1,|M|\}$, and the largest value not above $|M|$ is $r'$, with $r(G)\le r'$. The last statements follow from $\tau/2\le|M|\le\tau$. \end{proof} \begin{Proposition}[$c_1$] \label{prop:c1} For every graph $G$ without isolated vertices, $c_1$ is a minimal vertex cover, computed in $O((n+m)\,\alpha(n))$ time. \end{Proposition} \begin{proof} The decoded set is completed by a greedy cover of the uncovered edges and pruned, so $c_1$ is a cover, minimal by Theorem~\ref{thm:minimal}. The time is part of Theorem~\ref{thm:runtime}. \end{proof} No bound in terms of $\tau$ is proved for $c_1$ alone, and on some small graphs of Section~\ref{sec:car-bound} it exceeds $\frac32\tau$: the decoding may select, in a matched edge of the split graph, the endpoint that a minimum cover avoids. Its role in the ensemble is to supply a cover built from a different matching structure, and the bound of Theorem~\ref{thm:twotau} for the returned cover comes from $c_2$. \subsection{A per-instance $3/2$ certificate} \label{sec:cert} By Lemma~\ref{lem:rprime}, the inequality $|C|\le2\tau-|M|$, which would be the analogue of Theorem~\ref{thm:twotau} with $|M|$ components in place of $r$, implies the ratio $3/2$, since $|M|\ge\tau/2$, and it implies $|C|\le2\tau-r'$ for the split graph of $c_1$, since $r'\le|M|$. It involves the unknown optimum, so it cannot be tested while the algorithm runs. A lower bound on $\tau$ turns it into a test that can. \begin{Proposition}[Per-instance certificate] \label{prop:cert} Let $C$ be a vertex cover of $G$, $M$ the maximal matching of $c_2$, and $L\le\tau(G)$ any lower bound. \begin{enumerate} \item[(i)] If $|C|\le\frac32L$, then $|C|\le\frac32\tau(G)$. \item[(ii)] If $|C|\le2L-|M|$, then $|C|\le2\tau(G)-|M|\le\frac32\tau(G)$. \item[(iii)] The test of~(ii) implies the test of~(i): $2L-|M|\le\frac32L$. \end{enumerate} \end{Proposition} \begin{proof} (i) and the first inequality of~(ii) follow from $L\le\tau$; the second inequality of~(ii) is $|M|\ge\tau/2$ (Lemma~\ref{lem:rprime}). For~(iii), $2L-|M|\le\frac32L$ is equivalent to $L\le2|M|$, which holds because $L\le\tau\le2|M|$. \end{proof} Proposition~\ref{prop:cert} is a certificate, not a guarantee: it never certifies a false ratio, but it can fail to certify a true one when $L$ is weak. Test~(ii) certifies the conjectured bound itself, and test~(i) certifies only the ratio $3/2$. Both need a lower bound stronger than $|M|$: with $L=|M|$, test~(ii) reads $|C|\le|M|$, which holds only when $C$ is optimal and $\tau=|M|$. Suitable lower bounds that can be computed in polynomial time are the size of a Karp--Sipser matching~\cite{karp1981maximum}, of a maximum matching, which equals $\tau$ on bipartite graphs by K\H{o}nig's theorem~\cite{konig1931graphen} and is found there by the Hopcroft--Karp algorithm~\cite{hopcroft1973algorithm}, a packing of vertex-disjoint cliques $K_1,\dots,K_t$, which gives $\tau\ge\sum_i(|K_i|-1)$, and, on regular graphs, Hoffman's ratio bound~\cite{hoffman1970eigenvalues}. On bipartite graphs the certificate is therefore exact. \begin{Lemma}[The ratio $|M|/L$] \label{lem:rL} Let $L$ be a lower bound with $|M|\le L\le\tau(G)$, for instance the largest of $|M|$ and the bounds above. Then \[ \frac12\ \le\ \frac{|M|}{L}\ \le\ 1,\qquad\text{so the target }T=2L-|M|=L\Bigl(2-\frac{|M|}{L}\Bigr)\text{ satisfies }L\le T\le\tfrac32L. \] If a cover $C$ passes the test $|C|\le T$, then $|C|/\tau(G)\le\min\{|C|/L,\ 2-|M|/\tau(G)\}\le\frac32$. \end{Lemma} \begin{proof} $|M|\le L$ gives $|M|/L\le1$, and $L\le\tau\le2|M|$ gives $|M|/L\ge1/2$; hence $T\in[L,\frac32L]$. If $|C|\le T$, then $|C|/\tau\le|C|/L$ because $L\le\tau$, and $|C|\le2\tau-|M|$ by Proposition~\ref{prop:cert}(ii). \end{proof} Lemma~\ref{lem:rL} bounds the target, not the cover. The value of $|M|/L$ also shows how demanding the test is on a given instance: when $|M|/L$ is close to $1/2$ the threshold is close to $\frac32L$, and when $|M|/L=1$ the test passes only if $|C|=L=\tau$. Section~\ref{sec:car-bound} reports it on every instance. \subsection{The conjectures} \label{sec:conjectures} \begin{Conjecture}[Ensemble bound] \label{conj:ensemble} For every graph $G$ without isolated vertices, the cover $C$ returned by Algorithm~\ref{alg:main}, with $M$ the maximal matching of $c_2$, satisfies \[ |C|\ \le\ 2\,\tau(G)-|M|,\qquad\text{equivalently}\qquad |C|-\tau(G)\ \le\ \tau(G)-|M|. \] \end{Conjecture} \begin{Conjecture}[Universal $(2-\varepsilon_0)$-approximation] \label{conj:twoeps} For every graph $G$, Algorithm~\ref{alg:main} returns a vertex cover $C$ with $|C|\le1.999999999\,\tau(G)$. \end{Conjecture} By Lemma~\ref{lem:rprime}, Conjecture~\ref{conj:ensemble} implies $|C|\le\frac32\tau(G)$ and $|C|\le2\tau(G)-r'$ on every graph, and hence Conjecture~\ref{conj:twoeps}; by Corollary~\ref{cor:billion}, Conjecture~\ref{conj:twoeps} is a theorem on every graph with $\tau\le10^{9}r$ and is open only on graphs with more than $10^{9}$ vertices. Conjecture~\ref{conj:ensemble} would also give a lower bound on $\tau$ that is computable in polynomial time, $\tau\ge(|C|+|M|)/2$. Conjecture~\ref{conj:ensemble} is a statement about the ensemble, not about any single strategy: on the small graphs of Section~\ref{sec:car-bound} both $c_1$ and $c_2$ alone violate it, on a graph with six vertices for the first and four for the second, while the returned cover satisfies it on every instance. The second form shows how demanding it is. The excess of $C$ over the optimum must not exceed the gap $\tau-|M|$ between the optimum and the maximal matching. When $|M|$ is close to $\tau/2$, as in a graph made of disjoint triangles with one matched edge each, the conjecture asks only for the ratio $3/2$; when $|M|=\tau$, which happens whenever the maximal matching is maximum and $\tau=\nu$, as in many bipartite graphs, it asks for an \emph{optimal} cover. If UGC holds in the form of~\cite{khot2008vertex} and $\mathrm{P}\neq\mathrm{NP}$, then Conjecture~\ref{conj:ensemble} is false (Theorem~\ref{thm:pnp}), and since a polynomial-time algorithm that failed on finitely many graphs could be patched by a lookup table, it then fails on infinitely many graphs. Such graphs cannot be NO-type instances of the reduction of Khot and Regev: a graph with no independent set of more than $\delta n$ vertices, $\delta\le1/4$, has $\tau\ge(1-\delta)n$ and $|M|\le n/2$, so every cover satisfies $|C|-\tau\le\delta n\le(\tfrac12-\delta)n\le\tau-|M|$. A counterexample must be a YES-type instance, with an independent set of almost half the vertices, on which the excess of $C$ exceeds the gap $\tau-|M|$. The graphs of Section~\ref{sec:suite} are far smaller than the asymptotic instances of the reduction, so they test the conjecture, they do not prove it. \subsection{Conditional consequence for P versus NP} \label{sec:pnp} \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:ensemble} or Conjecture~\ref{conj:twoeps} is proved, then $\mathrm{P}=\mathrm{NP}$. The assumption holds if UGC holds~\cite{khot2008vertex}, and in particular if the Unique Games Theorem reported in~\cite{openai2026ugc} holds; without any assumption, a proof of either conjecture would refute UGC unless $\mathrm{P}=\mathrm{NP}$. \end{Theorem} \begin{proof} Algorithm~\ref{alg:main} runs in linear time (Theorem~\ref{thm:runtime}). A proof of Conjecture~\ref{conj:ensemble} makes it a polynomial-time $\frac32$-approximation, by Lemma~\ref{lem:rprime}, and a proof of Conjecture~\ref{conj:twoeps} makes it a polynomial-time $1.999999999$-approximation. Both ratios are of the form $2-\varepsilon_0$ with $\varepsilon_0>0$, so under the assumption the algorithm decides an NP-hard problem in polynomial time. The theorem of Khot and Regev~\cite{khot2008vertex} derives the assumption from UGC. \end{proof} \begin{Remark} \label{rem:pnp} Theorem~\ref{thm:pnp} is a conditional implication, not a proof of $\mathrm{P}=\mathrm{NP}$. The theorem of~\cite{openai2026ugc} was released in October 2026 with Lean artifacts and had not been peer reviewed at the time of writing; we cite it as reported and have not checked the formalization. The ratio $3/2$ lies above the unconditional NP-hardness threshold $\sqrt2-\varepsilon$ of~\cite{khot2018pseudorandom}, so Conjecture~\ref{conj:ensemble} contradicts no hardness result that is known without UGC. The only bounds proved here for all graphs are $2$ and $2-r/\tau$ (Theorems~\ref{thm:ratio2} and~\ref{thm:twotau}), neither of which is a constant below $2$. \end{Remark} \section{Runtime Analysis} \label{sec:runtime} \begin{Theorem} \label{thm:runtime} With the default parameters, every strategy $c_1,\dots,c_{17}$ of Algorithm~\ref{alg:main} runs in $O(n+m)$ time, except $c_1$ and $c_7$, which run in $O((n+m)\,\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function. Hence the whole algorithm runs in $O((n+m)\,\alpha(n))$ time. \end{Theorem} \begin{proof} Preprocessing and every pruning pass are single scans, $O(n+m)$. \emph{Base strategies.} The matching of $c_2$, which is also the matching $M$ of $c_1$, and the primal-dual scan of $c_6$ are single scans of the edges. In $c_1$ the union-find pass of Algorithm~\ref{alg:split} makes $O(m)$ operations, $O((n+m)\alpha(n))$ with union by size and path compression~\cite{tarjan1975efficiency}; the split graph has $m$ edges and at most $2n$ nodes; the edges of $M$ and the matched edges of $H$ are ordered by counting sorts on positions, since the first endpoints within each class are distinct; the matching of $H$ is one scan, and each of the three decodings, completions by a bucket queue and prunings is $O(n+m)$. The bucket queues of $c_3$, $c_5$ and the residual variant of $c_8$ receive $O(n+m)$ pushes, one per vertex and per degree decrement, and every pop costs $O(1)$; the minimum-bucket pointer of $c_5$ and $c_8$ moves down by at most one per deletion. In $c_4$ each auxiliary edge is inspected at most twice. In $c_7$ the spanning-forest core is built by union-find in $O((n+m)\alpha(n))$, the gadget is a forest with $O(n)$ nodes, and at the default parameter the Baker pass is its greedy baseline, which buckets the nodes by their three weights. The auxiliary graph of $c_8$ has $2m$ nodes in disjoint cycles and edges, solved by a dynamic program linear in its size. In $c_9$ a layer is built from the edges left in time linear in their number, and every layer takes at least half of them (Proposition~\ref{prop:c9}), so all layers together cost $O(n+m)$; a solve of a layer runs a matching scan, at most $p=8$ Hopcroft--Karp phases of linear cost~\cite{hopcroft1973algorithm} and two breadth-first searches, and each of at most $q=6$ orders solves every layer once, so $c_9$ costs $O(pq(n+m))$. The dynamic programs of $c_{10}$ and $c_{12}$ and the folding of $c_{11}$ charge every table entry and adjacency scan to work counters and stop at fixed multiples of $n+m$: $1024$ times the gadget size for $c_{10}$, whose bags have at most six nodes, $256(n+m)$ for $c_{12}$, whose width is at most $10$, and $4(n+m)$ for folding; the reductions of $c_{11}$ run on bucket queues of residual degrees. \emph{Improvers.} The union of $c_{13}$ has at most $n$ vertices. The local searches of $c_{14}$ and $c_{15}$ and the refinement $c_{17}$ stop after $100(n+m)$ work per call, sorting included; each of the three rounds of $c_{15}$ and of $c_{16}$ costs $O(n+m)$, and the votes of $c_{16}$ cost $O(\sum_i|c_i|)=O(n)$. Summing a constant number of these terms gives the claim. \end{proof} The constants are large: the work budgets alone allow a few hundred passes over the graph, and Section~\ref{sec:scaling} measures how the running time grows in practice. Larger limits, such as a smaller $\varepsilon$ for the Baker pass of $c_7$, unbounded refinement, or numbers of phases or orders of $c_9$ that grow with the graph, are available as options and give up the linear bound. \section{Reproducible Experiments} \label{sec:suite} \subsection{Setup} Every number in this section comes from running all the experiment scripts of the folder \texttt{car/} of the repository in quick mode, with the option \texttt{-{}-quick}, using \texttt{Salvador} 0.1.4 from the repository, Python 3.12.3 and NetworkX 3.6.1 on Windows~11; the comparison with Hvala on the DIMACS benchmarks (Section~\ref{sec:hvala-comparison}) comes from a run of the command-line program of the package on those files. Table~\ref{tab:quick} lists the scripts, the options they were run with and their time, $2{,}750$ seconds in total. Except for the small graphs of Part~A, every instance is built and solved in a worker process with a time limit, and is skipped if it exceeds it; no instance was skipped. Instances are generated from a fixed seed and their name alone, so that every instance can be rebuilt independently of the others. \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|l|l|r|} \hline \textbf{Script} & \textbf{Options used by \texttt{-{}-quick}} & \textbf{Measures} & \textbf{Time (s)} \\ \hline \texttt{car\_ratio.py} & \texttt{-{}-max-n 5000 -{}-timeout 120} & approximation ratio, Parts~A and~B & 102.5 \\ \hline \texttt{car\_strategies.py} & \texttt{-{}-max-n 5000} & which strategy wins; improvement chain & 106.6 \\ \hline \texttt{car\_c11\_variants.py} & \texttt{-{}-max-n 5000} & the six variants of $c_{11}$ & 123.7 \\ \hline \texttt{car\_c10\_bags.py} & & bags and exactness of $c_{10}$, Part~G & 135.6 \\ \hline \texttt{car\_c1\_components.py} & \texttt{-{}-max-n 5000} & the split graph and the ensemble bound, Part~I & 130.1 \\ \hline \texttt{car\_c1\_fix.py} & & the bound for single strategies, Part~I & 1.2 \\ \hline \texttt{car\_c9\_layers.py} & & the bipartite layers, Part~J & 2.6 \\ \hline \texttt{car\_regular.py} & & regular graphs, Part~F & 22.7 \\ \hline \texttt{car\_bipartite.py} & \texttt{-{}-max-n 1000} & bipartite graphs, Part~C & 221.3 \\ \hline \texttt{car\_yes\_instances.py} & \texttt{-{}-max-n 1280 -{}-exact-time 20} & Khot--Regev YES instances, Part~D & 628.1 \\ \hline \texttt{car\_mechanism.py} & \texttt{-{}-exact-time 20} & certificates and mechanism, Part~E & 179.3 \\ \hline \texttt{car\_triangle\_free.py} & \texttt{-{}-max-n 2000 -{}-exact-time 20 -{}-timeout 120} & triangle-free graphs, Part~H & 738.4 \\ \hline \texttt{car\_scaling.py} & \texttt{-{}-max-n 8000} & running time against $n+m$ & 354.0 \\ \hline \texttt{car\_ratio\_timing.py} & & time of each strategy on Part~A & 3.2 \\ \hline \end{tabular}% } \caption{The experiment scripts run in quick mode, the options added to \texttt{-{}-quick}, and their time. \texttt{-{}-max-n} caps the number of vertices, \texttt{-{}-exact-time} the seconds given to the integer program that proves $\tau$, and \texttt{-{}-timeout} the limit per instance.} \label{tab:quick} \end{table} \subsection{Parts A and B: small graphs and large adversarial graphs} Part~A collects $298$ small graphs whose optimum is known by K\H{o}nig's theorem or by branch and bound: $202$ graphs of order at most $7$ from the graph atlas, $12$ bipartite hill-climbing instances, $30$ random general graphs with $n\le12$, $25$ random bipartite graphs, $16$ bipartite grids, $12$ relabelling stress instances and one bipartite obstruction. Every returned cover is valid and optimal; the part took $2.1$ seconds. Part~B uses graphs with up to $5{,}000$ vertices, where we report $|C|/L$ for a certified lower bound $L\le\tau$, the largest of: a Hopcroft--Karp maximum matching on bipartite graphs, which gives $L=\tau$ by K\H{o}nig's theorem~\cite{konig1931graphen,hopcroft1973algorithm}; the NetworkX minimum maximal matching and a Karp--Sipser matching~\cite{karp1981maximum}; a greedy packing of vertex-disjoint cliques $K_i$, with $\tau\ge\sum_i(|K_i|-1)$; and a spectral bound, $\tau\ge n-\lfloor n(1-\delta/\mu_{\max})\rfloor$ with $\delta$ the minimum degree and $\mu_{\max}$ the largest Laplacian eigenvalue, which on regular graphs is Hoffman's bound~\cite{hoffman1970eigenvalues}; $\mu_{\max}$ is computed by Lanczos iteration, inflated by its residual and capped by $\max_{uv}(\deg u+\deg v)$. Table~\ref{tab:car-large} gives the results. \begin{table}[!htbp] \centering \footnotesize \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|l|r|r|} \hline \textbf{Family} & \textbf{Max $n$} & \textbf{Max ratio u.b.} & \textbf{Bound} & \textbf{Matching-only} & \textbf{Max time (s)} \\ \hline Random 12-regular & 5{,}000 & 1.1649 & spectral & 1.564 & 4.58 \\ \hline Random 6-regular & 5{,}000 & 1.1408 & spectral & 1.399 & 3.00 \\ \hline Random 3-regular & 5{,}000 & 1.0722 & spectral & 1.233 & 2.00 \\ \hline Sparse Erd\H{o}s--R\'enyi (deg.\ 4) & 5{,}000 & 1.0635 & Karp--Sipser & 1.253 & 2.24 \\ \hline Watts--Strogatz small-world & 5{,}000 & 1.0536 & clique packing & 1.417 & 2.39 \\ \hline Barab\'asi--Albert scale-free & 5{,}000 & 1.0078 & Karp--Sipser & 1.354 & 2.85 \\ \hline Complete bipartite & 800 & 1.0000 & exact & 1.000 & 31.37 \\ \hline Crown graph & 800 & 1.0000 & exact & 1.000 & 29.20 \\ \hline Double star + bridge & 2{,}002 & 1.0000 & exact & 1.000 & 0.74 \\ \hline \end{tabular}% } \caption{Part B: certified ratio upper bound $|C|/L$ on the $11$ instances of nine families, the lower bound that attained it, the bound the minimum maximal matching alone would give, and the time of the slowest instance.} \label{tab:car-large} \end{table} The certified ratio never exceeds $1.1649$, on the random $12$-regular graph with $5{,}000$ vertices, where the cover has $3{,}751$ vertices and the spectral bound certifies $\tau\ge3{,}220$; with the matching alone it would be $1.564$. The part took $98$ seconds. With Part~A, the exact or certified ratio never exceeds $1.17$. \subsection{Which strategy wins} \label{sec:winners} The strategy report runs the families of Parts~A and~B up to $n=5{,}000$, $297$ instances, and checks every candidate. Among the base strategies, $c_{12}$, which starts from the best of $c_1,\dots,c_{11}$, attains the smallest base cover on all $297$ instances and is the only one to do so on two; $c_{11}$ attains it on $295$, $c_{10}$ on $291$, $c_9$ on $287$, $c_5$ and $c_8$ on $284$, $c_3$ on $276$, $c_1$ on $275$, $c_4$ on $265$, $c_7$ on $264$, and $c_2$ and $c_6$ on $251$. Among the strategies that use earlier covers, $c_{11}$ strictly improved the best of $c_1,\dots,c_{10}$ on $6$ instances, by $183$ vertices in total, $c_{12}$ the best of $c_1,\dots,c_{11}$ on $2$, by $3$, the local search $c_{14}$ the best of $c_1,\dots,c_{13}$ on $5$, by $133$, and $c_{15}$ the best of $c_1,\dots,c_{14}$ on $5$, by $25$, of which $22$ came from its swap searches and $3$ from its reductions; $c_{10}$, $c_{16}$ and $c_{17}$ never improved their reference, and the union $c_{13}$ was larger than the best earlier cover on $43$ instances and never smaller. Table~\ref{tab:improvers} gives the improvement chain on the six large random graphs. \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|r|} \hline \textbf{Instance ($n=5{,}000$)} & \textbf{$c_1$} & \textbf{Best $c_2..c_8$} & \textbf{$c_9$} & \textbf{$c_{11}$} & \textbf{$c_{12}$} & \textbf{$c_{14}$} & \textbf{$c_{15}$} & \textbf{search} & \textbf{reduce} & \textbf{forced} & \textbf{$L$} & \textbf{$c_{17}$} \\ \hline Random 3-regular & 3{,}118 & 2{,}838 & 2{,}886 & 2{,}772 & 2{,}771 & 2{,}765 & 2{,}761 & 2 & 2 & 1{,}428 & 2{,}498 & 2{,}761 \\ \hline Random 6-regular & 3{,}582 & 3{,}355 & 3{,}429 & 3{,}332 & 3{,}332 & 3{,}280 & 3{,}274 & 6 & 0 & 2{,}318 & 2{,}499 & 3{,}274 \\ \hline Random 12-regular & 4{,}012 & 3{,}826 & 3{,}943 & 3{,}810 & 3{,}810 & 3{,}761 & 3{,}751 & 10 & 0 & 3{,}384 & 2{,}498 & 3{,}751 \\ \hline Sparse Erd\H{o}s--R\'enyi & 2{,}743 & 2{,}640 & 2{,}716 & 2{,}600 & 2{,}600 & 2{,}598 & 2{,}597 & 0 & 1 & 2{,}103 & 2{,}442 & 2{,}597 \\ \hline Watts--Strogatz & 3{,}715 & 3{,}605 & 3{,}661 & 3{,}569 & 3{,}567 & 3{,}543 & 3{,}539 & 4 & 0 & 2{,}988 & 2{,}491 & 3{,}539 \\ \hline Barab\'asi--Albert & 2{,}580 & 2{,}467 & 2{,}581 & 2{,}465 & 2{,}465 & 2{,}465 & 2{,}465 & 0 & 0 & 2{,}028 & 2{,}446 & 2{,}465 \\ \hline \end{tabular}% } \caption{Improvement chain on the six large random graphs: $c_1$, the best of $c_2,\dots,c_8$, $c_9$, $c_{11}$, $c_{12}$ (here $c_{10}$ equals its reference, the graphs being non-bipartite), $c_{14}$, $c_{15}$ (with the vertices removed by its swap searches and its reductions), the vertices forced in the last round of $c_{16}$ with its matching lower bound $L$, and the returned cover $c_{17}$.} \label{tab:improvers} \end{table} On these graphs the minimum-degree strategies $c_5$ and $c_8$ give the best independent cover, the reductions of $c_{11}$ remove $2$ to $66$ more vertices, and the local search of $c_{14}$, which starts from the best of all base strategies, removes up to $52$; consensus forcing fixes $28\%$ to $68\%$ of the vertices but finds no smaller cover. The exact strategies certify their own optimality often: $c_{12}$ has an empty core on $287$ of the $297$ instances, $c_{11}$ needs no peel on $223$, $c_{10}$ has an empty core on $109$ of the $116$ instances whose components are all bipartite, and the phases of $c_9$ end with a maximum matching on every bipartite instance; on the large random families the core of $c_{12}$ holds most of the vertices and $c_{11}$ peels up to half of them. The six variants of $c_{11}$ (peel \texttt{max}, \texttt{ref} or \texttt{min}, with or without folding) were compared with the best of $c_1,\dots,c_{10}$ on the same $297$ instances: folding raises the instances that need no peel from $168$ to $223$; \texttt{ref} and \texttt{ref+fold} are never worse and save $117$ and $132$ vertices; \texttt{max+fold} is worse on $2$ instances and saves $80$; and \texttt{min}, which does not satisfy $|S|\le\tau+p$, is worse on $6$. The ensemble uses \texttt{max+fold} and \texttt{ref+fold}. \subsection{Ablation} \label{sec:ablation} Every strategy sees the covers found before it, so the contribution of each group of strategies can be read off one run (Table~\ref{tab:ablation}). \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|l|r|r|r|r|r|r|r|} \hline \textbf{Experiment} & \textbf{Inst.} & \textbf{Measure} & \textbf{Best $c_1..c_{10}$} & \textbf{$+c_{11}$} & \textbf{$+c_{12},c_{13}$} & \textbf{$+c_{14}$} & \textbf{$+c_{15}$} & \textbf{$+c_{16}$} & \textbf{Final $c_{17}$} \\ \hline Bipartite graphs (Part C) & 108 & optimal & 106 & 108 & 108 & 108 & 108 & 108 & 108 \\ & & total excess & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline Mechanism (Part E), $\tau$ known & 34 & optimal & 22 & 28 & 28 & 29 & 29 & 30 & 31 \\ & & total excess & 55 & 42 & 42 & 21 & 20 & 17 & 15 \\ \hline Khot--Regev YES (Part D), $\tau$ known & 16 & optimal & 1 & 7 & 7 & 13 & 13 & 13 & 13 \\ & & total excess & 128 & 54 & 54 & 9 & 9 & 9 & 9 \\ \hline Khot--Regev YES (Part D), all & 38 & cover $-$ planted & $-503$ & $-673$ & $-673$ & $-815$ & $-831$ & $-832$ & $-841$ \\ \hline Regular graphs (Part F), general & 26 & total cover & 3{,}978 & $-25$ & $0$ & $-34$ & $-4$ & $0$ & $0$ \\ \hline Large random graphs (strategy report) & 6 & total cover & 18{,}731 & $-183$ & $-3$ & $-133$ & $-25$ & $0$ & $0$ \\ \hline \end{tabular}% } \caption{Ablation. Each column adds strategies to the previous ones; ``optimal'' counts covers of size $\tau$, ``total excess'' is $\sum(|C|-\tau)$, and the rows ``total cover'' give the size of the best of $c_1,\dots,c_{10}$ and then the change made by each addition.} \label{tab:ablation} \end{table} The base strategies $c_1,\dots,c_{10}$ already solve $106$ of the $108$ bipartite graphs, and the reductions of $c_{11}$ solve the other two. On the Khot--Regev YES instances and on the mechanism instances the base strategies are weak, and the reductions of $c_{11}$ and the local search of $c_{14}$ do most of the work: together they reduce the total excess on the YES instances with known optimum from $128$ to $9$. Consensus forcing and the refinement still help on the mechanism instances, where they make two more covers optimal. No strategy ever made the returned cover larger, as the guards of Algorithm~\ref{alg:main} guarantee. \subsection{Part C: bipartite graphs} \label{sec:car-bipartite} On bipartite graphs $\tau=\nu$, so Theorem~\ref{thm:matching} gives only the ratio $2$, while by Theorem~\ref{thm:posterior} the measured ratio is the exact a-posteriori certificate. Part~C runs $108$ bipartite graphs of $15$ families with up to $1{,}000$ vertices and shuffled labels, and computes $\tau=\nu$ by Hopcroft--Karp for measurement only (Table~\ref{tab:car-bipartite}). \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Inst.} & \textbf{Max $n$} & \textbf{Opt.\ $c_1..c_{10}$} & \textbf{Opt.\ $c_9$} & \textbf{Optimal} & \textbf{Max ratio} & \textbf{Exc.\ $c_1..c_{10}$} & \textbf{Excess} & \textbf{$c_9$ exact} & \textbf{$c_{10}$ exact} & \textbf{$c_{12}$ exact} \\ \hline Random bipartite (balanced) & 18 & 1{,}000 & 17 & 17 & 18 & 1.0000 & 2 & 0 & 17 & 0 & 0 \\ \hline Random bipartite (1:2) & 18 & 1{,}000 & 18 & 18 & 18 & 1.0000 & 0 & 0 & 18 & 0 & 0 \\ \hline Random $d$-regular bipartite & 18 & 1{,}000 & 18 & 18 & 18 & 1.0000 & 0 & 0 & 18 & 0 & 0 \\ \hline Power-law bipartite & 6 & 1{,}000 & 6 & 6 & 6 & 1.0000 & 0 & 0 & 6 & 0 & 3 \\ \hline Double cover $G\times K_2$ & 12 & 1{,}000 & 12 & 12 & 12 & 1.0000 & 0 & 0 & 12 & 0 & 0 \\ \hline Hidden perfect matching & 12 & 1{,}000 & 12 & 12 & 12 & 1.0000 & 0 & 0 & 9 & 0 & 3 \\ \hline Random tree & 6 & 1{,}000 & 6 & 6 & 6 & 1.0000 & 0 & 0 & 6 & 6 & 6 \\ \hline 2D grid, $70\%$ of edges & 6 & 961 & 5 & 5 & 6 & 1.0000 & 1 & 0 & 5 & 2 & 3 \\ \hline 2D grid & 2 & 961 & 2 & 2 & 2 & 1.0000 & 0 & 0 & 2 & 0 & 0 \\ \hline 3D grid & 2 & 1{,}000 & 2 & 2 & 2 & 1.0000 & 0 & 0 & 2 & 0 & 0 \\ \hline Even cycle & 2 & 1{,}000 & 2 & 2 & 2 & 1.0000 & 0 & 0 & 1 & 2 & 2 \\ \hline Complete bipartite & 2 & 1{,}000 & 2 & 2 & 2 & 1.0000 & 0 & 0 & 2 & 0 & 0 \\ \hline Crown graph & 2 & 1{,}000 & 2 & 2 & 2 & 1.0000 & 0 & 0 & 2 & 0 & 0 \\ \hline Hypercube & 1 & 256 & 1 & 1 & 1 & 1.0000 & 0 & 0 & 1 & 0 & 0 \\ \hline Hypercube, $50\%$ of edges & 1 & 256 & 1 & 1 & 1 & 1.0000 & 0 & 0 & 1 & 0 & 0 \\ \hline \textbf{All} & \textbf{108} & \textbf{1{,}000} & \textbf{106} & \textbf{106} & \textbf{108} & \textbf{1.0000} & \textbf{3} & \textbf{0} & \textbf{102} & \textbf{10} & \textbf{17} \\ \hline \end{tabular}% } \caption{Part C: the returned cover on $108$ bipartite graphs against $\tau=\nu$; ``Opt.'' and ``Exc.'' count optimal instances and total excess of the best of $c_1,\dots,c_{10}$, of $c_9$ and of the returned cover; ``$c_9$ exact'' counts the instances on which the phases of $c_9$ end with a maximum matching, and the last two columns the empty cores of $c_{10}$ and $c_{12}$.} \label{tab:car-bipartite} \end{table} The ensemble returned a minimum cover on all $108$ graphs, $26{,}523$ vertices in total. The phases of $c_9$ end with a maximum matching on $102$ graphs, where $c_9$ is optimal by Proposition~\ref{prop:c9}(iii); it is optimal on $106$, and on the other two, a random balanced bipartite graph and a thinned grid, it is two and one vertices above $\tau$. Every regular bipartite graph, double cover, tree, grid, cycle, complete bipartite graph, crown graph and hypercube was solved exactly, as Theorem~\ref{thm:degsep} predicts for the $19$ regular and degree-separated ones. The part took $221$ seconds. \subsection{Part D: YES-type instances of the Khot--Regev reduction} \label{sec:car-yes} 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\}$ spans edges only on violated constraints, and removing one endpoint of each leaves an independent set whose complement is a \emph{planted cover} of about $(1-p)n$ vertices. The base family has $k=4$, $p=0.45$, $\eta=0$, $d=4$, $s=16$; nine more change one parameter. With $N\in\{40,80\}$ and two seeds this gives $38$ instances with $640$ to $1{,}280$ vertices. The lower bound is the larger of the linear relaxation and the bound of an integer program (HiGHS, $20$ seconds), which proved $\tau$ on $16$ instances (Table~\ref{tab:car-yes}). \begin{table}[!htbp] \centering \scriptsize \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Inst.} & \textbf{$\le$ planted} & \textbf{$\tau$ known} & \textbf{Opt.\ $c_1..c_{10}$} & \textbf{Optimal} & \textbf{Max exact} & \textbf{Max cert.} \\ \hline Base family & 4 & 3 & 1 & 0 & 1 & 1.0000 & 1.0502 \\ \hline Label size $k=3$ & 4 & 4 & 0 & 0 & 0 & -- & 1.0731 \\ \hline Label size $k=6$ & 4 & 4 & 4 & 0 & 4 & 1.0000 & 1.0000 \\ \hline Bias $p=0.35$ & 4 & 4 & 0 & 0 & 0 & -- & 1.1606 \\ \hline Bias $p=0.49$ & 4 & 4 & 4 & 0 & 4 & 1.0000 & 1.0000 \\ \hline Noise $\eta=0.02$ & 4 & 3 & 2 & 0 & 1 & 1.0089 & 1.0623 \\ \hline Noise $\eta=0.1$ & 4 & 4 & 1 & 0 & 0 & 1.0029 & 1.0381 \\ \hline Constraint degree $d=8$ & 4 & 3 & 2 & 1 & 2 & 1.0000 & 1.1149 \\ \hline Samples per block $s=32$ & 2 & 1 & 0 & 0 & 0 & -- & 1.0988 \\ \hline Linear UG, Max-$2$-Lin$(\mathbb{Z}_k)$ & 4 & 4 & 2 & 0 & 1 & 1.0148 & 1.0443 \\ \hline \textbf{All} & \textbf{38} & \textbf{34} & \textbf{16} & \textbf{1} & \textbf{13} & \textbf{1.0148} & \textbf{1.1606} \\ \hline \end{tabular}% } \caption{Part D: $38$ sampled Khot--Regev YES instances. ``$\le$ planted'' counts covers no larger than the planted one; ``Max exact'' is the largest $|C|/\tau$ where $\tau$ is known; ``Max cert.'' the largest $|C|/L$.} \label{tab:car-yes} \end{table} The cover is no larger than the planted one on $34$ instances and strictly smaller on $28$. Where $\tau$ is known it is optimal on $13$ of $16$, with mean ratio $1.0017$ and maximum $1.0148$, on a linear-constraint instance ($342$ against $337$; planted $347$); the certified ratio never exceeds $1.161$. The base strategies are optimal on only one of the $16$, and the ablation of Table~\ref{tab:ablation} shows that the reductions of $c_{11}$ and the local search of $c_{14}$ close almost all of the gap. The part took $628$ seconds, mostly in the integer programs. These instances are far from the asymptotic regime of the reduction, so they show only that \textsc{Salvador} stays within $1.5\%$ of the optimum where it is known. \subsection{Part E: certificates and mechanism} \label{sec:car-mechanism} Part~E runs $40$ instances of ten families with $140$ to $320$ vertices: sampled and fixed-weight Khot--Regev YES instances, regular graphs with a planted independent set, random regular graphs and thinned grids. It computes $\tau$ by an integer program, the linear relaxation, the Nemhauser--Trotter decomposition~\cite{nemhauser1975vertex}, the best term of $\beta(G)$ in Theorem~\ref{thm:combined}, the degree bias of a maximum independent set, and the best of the base strategies and the union, $\min_{i\le13}|c_i|$ (Table~\ref{tab:car-mechanism}). \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3.5pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{$\tau$ known} & \textbf{Opt.} & \textbf{Max exact} & \textbf{Max cert.} & \textbf{Max $\beta$} & \textbf{Bias} & \textbf{Base exc.} \\ \hline KR sampled $k=4$ & 4/4 & 3 & 1.0054 & 1.0054 & 1.798 & 0.858 & 0.87\% \\ \hline KR sampled $k=6$ & 4/4 & 4 & 1.0000 & 1.0000 & 1.902 & 0.933 & 0.00\% \\ \hline KR fixed $k=4,t=2$ (bip.) & 4/4 & 4 & 1.0000 & 1.0000 & 1.908 & 0.618 & 0.00\% \\ \hline KR fixed $k=5,t=2$ & 4/4 & 2 & 1.0938 & 1.0938 & 1.741 & 0.552 & 7.25\% \\ \hline KR fixed $k=6,t=3$ (bip.) & 4/4 & 4 & 1.0000 & 1.0000 & 1.734 & 0.786 & 0.00\% \\ \hline Planted regular $\alpha=0.45$, $d=6$ & 4/4 & 4 & 1.0000 & 1.0000 & 1.575 & 0.594 & 0.00\% \\ \hline Planted regular $\alpha=0.48$, $d=10$ & 4/4 & 4 & 1.0000 & 1.0000 & 1.743 & 0.631 & 0.00\% \\ \hline Random regular $d=3$ & 2/4 & 2 & 1.0000 & 1.0409 & 1.404 & 0.500 & 0.56\% \\ \hline Random regular $d=6$ & 0/4 & 0 & -- & 1.1436 & 1.514 & 0.500 & -- \\ \hline Thinned grid ($70\%$, bip.) & 4/4 & 4 & 1.0000 & 1.0000 & 1.450 & 0.660 & 0.00\% \\ \hline \textbf{All} & \textbf{34/40} & \textbf{31} & \textbf{1.0938} & \textbf{1.1436} & \textbf{1.908} & \textbf{0.663} & \textbf{0.99\%} \\ \hline \end{tabular}% } \caption{Part E: ``Max $\beta$'' is the largest a-priori certificate of Theorem~\ref{thm:combined}, always its Caro--Wei term; ``Bias'' the mean probability that a vertex of a maximum independent set has smaller degree than a vertex outside it; ``Base exc.'' the mean relative excess of $\min_{i\le13}|c_i|$ over $\tau$.} \label{tab:car-mechanism} \end{table} The a-priori certificate $\beta(G)$ is below $R_0$ on all $40$ instances, always through the Caro--Wei term of $c_8$, with maximum $1.908$, and no instance lies in $\mathcal{R}$. Maximum independent sets favour low-degree vertices (mean bias $0.663$, exactly $0.5$ on regular graphs), which is the choice of $c_5$ and $c_8$. The best of $c_1,\dots,c_{13}$ is $0.99\%$ above the optimum on average and optimal on $28$ of the $34$ instances with known $\tau$; the improvers improve it on $6$ and leave a mean excess of $0.44\%$, with $31$ of $34$ covers optimal. The hardest family is the fixed-weight Khot--Regev family with $k=5$, where two of four covers are not optimal and the largest ratio is $1.094$. No returned cover admits a $(1,2)$-swap. The Nemhauser--Trotter kernel covers $74\%$ of the vertices on average, so the linear relaxation fixes little, and its persistency is respected on all $40$ instances. The mean ratio is $1$ at both sizes $N=10$ and $N=20$ on six families; on the sampled family with $k=4$ it is $1$ and $1.0027$, on the fixed-weight family with $k=5$ it is $1.073$ and $1$, on the random $3$-regular graphs $1$ and $1.038$, and on the random $6$-regular graphs the certified bound grows from $1.087$ to $1.139$, where the integer program no longer proves $\tau$ and the bound comes from the weak relaxation. The part took $178$ seconds. \subsection{Part F: regular graphs of increasing degree} \label{sec:car-regular} For every $d\in\{3,4,5,6,8,10,12,16,20,24,32,48,64\}$, $n=200$ and two seeds, Part~F builds a random $d$-regular graph and a random $d$-regular bipartite graph. On the $26$ bipartite graphs every cover is optimal, and $c_5$, $c_8$ and $c_9$ are each exact on all of them alone, as Theorem~\ref{thm:degsep} requires for $c_5$ and $c_8$. Table~\ref{tab:car-regular} reports the general graphs, with the spectral lower bound, and compares with $1+2\sqrt{d-1}/d$, the value of Hoffman's bound $n/\tau\le1+|\lambda_{\min}|/d$ when $|\lambda_{\min}|=2\sqrt{d-1}$, which random regular graphs attain asymptotically~\cite{friedman2008proof}. \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3.5pt} \begin{tabular}{|r|r|r|r|r|r|r|} \hline \textbf{$d$} & \textbf{Max ratio u.b.} & \textbf{Mean ratio u.b.} & \textbf{$|C|/n$} & \textbf{$L/n$} & \textbf{vs.\ estimate} & \textbf{$1+\frac{2\sqrt{d-1}}{d}$} \\ \hline 3 & 1.0769 & 1.0721 & 0.558 & 0.520 & 2.083 & 1.943 \\ \hline 4 & 1.1101 & 1.1064 & 0.597 & 0.540 & 1.947 & 1.866 \\ \hline 5 & 1.1339 & 1.1339 & 0.635 & 0.560 & 1.783 & 1.800 \\ \hline 6 & 1.1466 & 1.1379 & 0.660 & 0.580 & 1.639 & 1.745 \\ \hline 8 & 1.1570 & 1.1564 & 0.702 & 0.607 & 1.463 & 1.661 \\ \hline 10 & 1.1484 & 1.1484 & 0.735 & 0.640 & 1.362 & 1.600 \\ \hline 12 & 1.1527 & 1.1478 & 0.758 & 0.660 & 1.293 & 1.553 \\ \hline 16 & 1.1606 & 1.1491 & 0.790 & 0.688 & 1.209 & 1.484 \\ \hline 20 & 1.1549 & 1.1509 & 0.820 & 0.712 & 1.171 & 1.436 \\ \hline 24 & 1.1507 & 1.1434 & 0.837 & 0.732 & 1.139 & 1.400 \\ \hline 32 & 1.1523 & 1.1448 & 0.870 & 0.760 & 1.111 & 1.348 \\ \hline 48 & 1.1250 & 1.1211 & 0.903 & 0.805 & 1.076 & 1.286 \\ \hline 64 & 1.1145 & 1.1114 & 0.923 & 0.830 & 1.060 & 1.248 \\ \hline \end{tabular} \caption{Part F: random $d$-regular graphs, $n=200$. ``vs.\ estimate'' is $|C|$ over the estimate $n(1-2\ln d/d)$ of $\tau$~\cite{frieze1992independence}, asymptotic in $d$ and not a bound.} \label{tab:car-regular} \end{table} The certified ratio never exceeds $1.1606$ ($d=16$) and does not grow with $d$, far below the bound $2-2/(d+1)$ of Theorem~\ref{thm:regular}; the covers approach the estimate of $\tau$ as $d$ grows. The part took $19$ seconds of solving time. \subsection{Part G: the bags and the exactness of $c_{10}$} \label{sec:car-bags} Part~G runs $c_{10}$ alone, with the pruned cover of the NetworkX minimum maximal matching as reference, on the $108$ bipartite graphs of Part~C, records the bags and the core, and computes the minor-min-width lower bound on the treewidth of the gadget (Table~\ref{tab:car-bags}); it also runs $c_{10}$ on $285$ random bipartite graphs with at most $14$ vertices and compares it by brute force with every minimum cover. \begin{table}[!htbp] \centering \scriptsize \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Inst.} & \textbf{Max bag} & \textbf{Exact} & \textbf{$|c_{10}|/\tau$} & \textbf{Ref.$/\tau$} & \textbf{Max tw LB} & \textbf{Time (s)} \\ \hline Random bipartite (balanced) & 18 & 3 & 0 & 1.649 & 1.808 & 69 & 8.61 \\ \hline Random bipartite (1:2) & 18 & 4 & 0 & 1.856 & 1.989 & 46 & 8.18 \\ \hline Random $d$-regular bipartite & 18 & 4 & 0 & 1.693 & 1.866 & 41 & 5.03 \\ \hline Power-law bipartite & 6 & 3 & 0 & 1.084 & 1.841 & 17 & 0.97 \\ \hline Double cover $G\times K_2$ & 12 & 3 & 0 & 1.660 & 1.858 & 30 & 2.37 \\ \hline Hidden perfect matching & 12 & 4 & 0 & 1.461 & 1.793 & 30 & 2.23 \\ \hline Random tree & 6 & 2 & 6 & 1.000 & 1.775 & 1 & 0.51 \\ \hline 2D grid, $70\%$ of edges & 6 & 6 & 2 & 1.110 & 1.897 & 5 & 2.36 \\ \hline 2D grid & 2 & 4 & 0 & 1.697 & 1.976 & 7 & 0.40 \\ \hline 3D grid & 2 & 3 & 0 & 1.941 & 1.996 & 15 & 0.54 \\ \hline Even cycle & 2 & 3 & 2 & 1.000 & 2.000 & 2 & 0.33 \\ \hline Complete bipartite & 2 & 4 & 0 & 2.000 & 2.000 & 5 & 28.54 \\ \hline Crown graph & 2 & 5 & 0 & 2.000 & 2.000 & 6 & 39.39 \\ \hline Hypercube & 1 & 3 & 0 & 1.953 & 1.953 & 19 & 0.12 \\ \hline Hypercube, $50\%$ of edges & 1 & 3 & 0 & 1.578 & 1.828 & 12 & 0.07 \\ \hline \textbf{All} & \textbf{108} & \textbf{6} & \textbf{10} & & & & \textbf{99.65} \\ \hline \end{tabular}% } \caption{Part G: $c_{10}$ alone. ``Exact'' counts empty cores; $|c_{10}|/\tau$ and ``Ref.$/\tau$'' are means; ``Max tw LB'' the largest lower bound on the treewidth of the gadget.} \label{tab:car-bags} \end{table} No bag exceeded six nodes. The core is empty on $10$ instances (trees, even cycles and two thinned grids), where the cover is optimal; on $84$ others the treewidth bound is at least $6$, so a core is unavoidable under the cap whatever the elimination order. Where the core is not empty, $c_{10}$ improves its reference on every family except the dense complete bipartite and crown graphs and the hypercube. On the $285$ small graphs the core was empty on $270$, and on all of them the cover was a minimum cover with the fewest doubly covered edges, as Proposition~\ref{prop:c10} states. The part took $100$ seconds, $68$ of them on the four dense graphs. \subsection{Part H: triangle-free graphs} \label{sec:car-tf} Part~H runs triangle-free graphs: named graphs (Petersen, Clebsch, Hoffman--Singleton and others), Mycielski, Andr\'asfai, Kneser $K(n,k)$ with $n<3k$, generalized Petersen graphs, middle-third circulants, small random graphs of the triangle-free process, and an adversarial hill climb that maximises the ratio against the optimum; and larger graphs: Khot--Regev YES instances on triangle-free constraint graphs, the triangle-free process with average degree $4$ to $32$, $G(n,p)$ with one edge of every triangle removed, random regular graphs with triangles switched out, Frankl--R\"odl graphs, and large Mycielski, Andr\'asfai and circulant graphs. Where $\tau$ is not proved, the true ratio lies in $[|C|/\tau_{\mathrm{upper}},|C|/L]$ (Table~\ref{tab:car-tf}). \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Inst.} & \textbf{Max $n$} & \textbf{$\tau$ known} & \textbf{Optimal} & \textbf{Max exact} & \textbf{Max lower} & \textbf{Max cert.} \\ \hline Small families with known optimum$^{a}$ & 161 & 64 & 161 & 161 & 1.0000 & 1.0000 & 1.0000 \\ \hline Khot--Regev on triangle-free constraint graphs$^{b}$ & 19 & 1{,}280 & 3 & 2 & 1.0016 & 1.0299 & 1.1839 \\ \hline Large Mycielski $M_8$--$M_{10}$ & 3 & 767 & 3 & 3 & 1.0000 & 1.0000 & 1.0000 \\ \hline Large Andr\'asfai graphs & 4 & 1{,}199 & 2 & 2 & 1.0000 & 1.0000 & 1.2165 \\ \hline Large middle-third circulants & 4 & 2{,}000 & 1 & 1 & 1.0000 & 1.0000 & 1.2174 \\ \hline Frankl--R\"odl $FR(q,t)$ & 2 & 1{,}024 & 0 & 0 & -- & 1.0000 & 1.1938 \\ \hline Triangle-free process, avg.\ deg.\ $4$--$32$ & 4 & 2{,}000 & 0 & 0 & -- & 1.0000 & 1.6970 \\ \hline $G(n,p)$, triangles removed, deg.\ $4$--$16$ & 3 & 2{,}000 & 0 & 0 & -- & 1.0000 & 1.5130 \\ \hline Random $d$-regular, triangle-free, $d=3$--$12$ & 5 & 2{,}000 & 0 & 0 & -- & 1.0000 & 1.1694 \\ \hline Random bipartite (control) & 1 & 1{,}996 & 1 & 1 & 1.0000 & 1.0000 & 1.0000 \\ \hline \textbf{All} & \textbf{206} & \textbf{2{,}000} & \textbf{171} & \textbf{170} & \textbf{1.0016} & \textbf{1.0299} & \textbf{1.6970} \\ \hline \end{tabular}% } \caption{Part H: $206$ triangle-free graphs. ``Max lower'' and ``Max cert.'' are the largest certified lower and upper bounds on the ratio. $^{a}$Named, Mycielski, Andr\'asfai, Kneser, generalized Petersen, circulant, random ($n\le40$) and hill-climb instances. $^{b}$Ten variants as in Part~D.} \label{tab:car-tf} \end{table} All $161$ small instances are solved optimally, and the hill climb finds no ratio above $1$. Among the $45$ large instances the optimum was proved on $10$, and the cover is optimal on $9$; the exception is a Khot--Regev instance with $p=0.49$ ($621$ against $620$, ratio $1.0016$). On the Khot--Regev triangle-free instances the certified upper bound is at most $1.184$. On the triangle-free process and the $G(n,p)$ graphs the only lower bound is the relaxation, about $n/2$, and the certified upper bound grows with the average degree to $1.70$ at degree $32$, while the lower bound stays at $1$: the intervals are wide because the relaxation is weak. The certified bound is at most $1.5$ on $203$ of the $206$ instances. These figures do not contradict the hardness of the class. By the triangle-removal argument recalled in the introduction, a polynomial-time $(2-\varepsilon)$-approximation on triangle-free graphs would give one on all graphs, so under UGC triangle-free graphs are as hard as general graphs in the worst case~\cite{bonnet2025string,khot2008vertex}. The ratios measured here, optimal on every small instance and certified at most $1.5$ on $203$ of the $206$ instances, describe the families generated in this part, not the worst case; the hard instances of the reduction are far larger, and if UGC holds and $\mathrm{P}\neq\mathrm{NP}$, then for every fixed $\varepsilon>0$ there are triangle-free graphs on which the cover of Algorithm~\ref{alg:main} exceeds $(2-\varepsilon)\tau$. The part took $738$ seconds. \subsection{Part I: the bound $2\tau-|M|$} \label{sec:car-bound} Part~I tests Conjecture~\ref{conj:ensemble} and the structure of the split graph of $c_1$. Its first script runs the ensemble on the $297$ non-adaptive instances of Parts~A and~B, $291$ of them with a known optimum, and checks $|C|\le2\tau-|M|$ for the returned cover; its second script checks the same bound, and $2\tau-r'$, for single strategies on $311$ small graphs with a known optimum, the $286$ non-adaptive graphs of Part~A and $25$ hand-made stress graphs on which a leaf-for-hub choice is expensive (paths, stars, double stars, spiders, caterpillars, brooms and $K_{2,k}$). On the six graphs without a known optimum, the bound is decided by the certificate of Proposition~\ref{prop:cert}(ii) (Table~\ref{tab:bound}). \begin{table}[!htbp] \centering \footnotesize \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline \textbf{Cover} & \textbf{Graphs with $\tau$} & \textbf{$>2\tau-|M|$} & \textbf{$>2\tau-r$} & \textbf{$>\frac32\tau$} & \textbf{Optimal} & \textbf{Max exact ratio} & \textbf{Certified} \\ \hline Returned cover $c_{17}$ & 291 & \textbf{0} & \textbf{0} & \textbf{0} & \textbf{291} & \textbf{1.0000} & \textbf{6 of 6} \\ \hline $c_1$ alone & 311 & 13 & 0 & 3 & 295 & 1.6667 & -- \\ \hline $c_2$ alone & 311 & 18 & 0 & 3 & 270 & 1.6667 & -- \\ \hline \end{tabular}% } \caption{Part I: the bound $2\tau-|M|$ for the returned cover on the instances of Parts~A and~B, and for $c_1$ and $c_2$ alone on the small graphs. ``Certified'' counts the graphs without a known optimum on which $|C|\le2L-|M|$.} \label{tab:bound} \end{table} The returned cover satisfies the bound on every instance, whereas $c_1$ and $c_2$ alone violate it on $13$ and $18$ small graphs; the smallest counterexamples have six vertices for $c_1$ ($\tau=3$, $|M|=3$, $|c_1|=4$) and four for $c_2$. The bound is therefore a property of the ensemble, as Conjecture~\ref{conj:ensemble} states, and not of either strategy. On $154$ of the graphs with a known optimum the maximal matching has $|M|=\tau$, so the conjecture requires an optimal cover; the returned cover was optimal on all of them, and $c_1$ on $141$. Over the $297$ instances $|M|/L$ lies between $0.500$ and $1.000$, as Lemma~\ref{lem:rL} requires, with mean $0.843$ and median $1.000$, and on $65\%$ of them $|M|/L\ge0.75$, so that the threshold $2-|M|/L$ is at most $1.25$. The split graph has $r'=|M|$ components on $282$ of the $297$ instances and $r'=|M|-1$ on the other $15$, as Lemma~\ref{lem:rprime} allows. \begin{table}[!htbp] \centering \footnotesize \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|l|r|r|r|r|r|r|} \hline \textbf{Instance} & \textbf{$n$} & \textbf{$m$} & \textbf{$L$} & \textbf{Bound} & \textbf{$|M|$} & \textbf{$2L-|M|$} & \textbf{$|C|$} & \textbf{$|M|/L$} & \textbf{$2-|M|/L$} & \textbf{$|C|/L$} \\ \hline Random 3-regular & 5{,}000 & 7{,}500 & 2{,}575 & spectral & 2{,}239 & 2{,}911 & 2{,}761 & 0.870 & 1.130 & 1.0722 \\ \hline Random 6-regular & 5{,}000 & 15{,}000 & 2{,}870 & spectral & 2{,}340 & 3{,}400 & 3{,}274 & 0.815 & 1.185 & 1.1408 \\ \hline Random 12-regular & 5{,}000 & 30{,}000 & 3{,}220 & spectral & 2{,}399 & 4{,}041 & 3{,}751 & 0.745 & 1.255 & 1.1649 \\ \hline Barab\'asi--Albert & 5{,}000 & 14{,}991 & 2{,}446 & Karp--Sipser & 1{,}821 & 3{,}071 & 2{,}465 & 0.744 & 1.256 & 1.0078 \\ \hline Sparse Erd\H{o}s--R\'enyi & 4{,}908 & 9{,}891 & 2{,}442 & Karp--Sipser & 2{,}072 & 2{,}812 & 2{,}597 & 0.848 & 1.152 & 1.0635 \\ \hline Watts--Strogatz & 5{,}000 & 15{,}000 & 3{,}359 & clique packing & 2{,}498 & 4{,}220 & 3{,}539 & 0.744 & 1.256 & 1.0536 \\ \hline \end{tabular}% } \caption{The six graphs without a known optimum. Every one is certified, $|C|/L\le2-|M|/L$, that is $|C|\le2L-|M|$, which proves $|C|\le2\tau-|M|\le\frac32\tau$ on that graph (Proposition~\ref{prop:cert} and Lemma~\ref{lem:rL}).} \label{tab:c1inexact} \end{table} All six are certified, with margins between $0.04$ and $0.25$ below the threshold; the smallest margins occur on the random regular graphs, where the spectral bound is the only good lower bound. \subsection{Part J: the bipartite layers} \label{sec:car-layers} Part~J runs the ensemble on $325$ small graphs with a known optimum: the $286$ non-adaptive graphs of Part~A and $39$ hand-made non-bipartite graphs and mixtures on which the layers matter (odd cycles, wheels, complete graphs, the Petersen and dodecahedral graphs, circulants, Mycielski graphs, triangular and king's grids, chains of odd cycles, and bipartite graphs with a few odd edges). On the $113$ bipartite graphs $c_9$ is a single layer, its phases end with a maximum matching, and it is optimal on all of them, as Proposition~\ref{prop:c9}(iii) states. On the $212$ non-bipartite graphs it uses two or three layers, never more than $\lfloor\log_2m\rfloor+1$, which is attained on the smallest graphs, and it is optimal on $203$; its largest ratio is $3/2$, on a graph of the atlas with five vertices. It is never smaller than every other candidate on these graphs, smaller than $c_2$ on $44$ and larger on $7$, and its refinement attains the final size on $324$ of the $325$. The returned cover is optimal on all $325$. \subsection{Part K: DIMACS clique complements, compared with Hvala} \label{sec:hvala-comparison} On the $68$ DIMACS clique-complement instances of NPBench~\cite{NPBench}, whose optimum is $n-\omega$ with the clique numbers compiled by Mascia~\cite{DIMACSClique} (best-known values for \texttt{C500.9} and \texttt{C1000.9}), we compare the figures reported for Hvala~\cite{Vega26Hvala} with one run of \textsc{Salvador} 0.1.4 at the default parameters. Table~\ref{tab:salvador-hvala} summarises by family. \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \begin{tabular}{|l|r|r|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Inst.} & \textbf{OPT} & \textbf{Hvala} & \textbf{Salvador} & \textbf{Wins} & \textbf{Opt.\ Hvala} & \textbf{Opt.\ Salvador} & \textbf{Max ratio H.} & \textbf{Max ratio S.} \\ \hline \texttt{brock} & 12 & 5{,}317 & 5{,}407 & 5{,}370 & 12 & 0 & 0 & 1.033 & 1.025 \\ \hline \texttt{c-fat} & 7 & 2{,}276 & 2{,}276 & 2{,}276 & 0 & 7 & 7 & 1.000 & 1.000 \\ \hline \texttt{C} & 4 & 1{,}672 & 1{,}705 & 1{,}681 & 4 & 0 & 1 & 1.039 & 1.007 \\ \hline \texttt{gen} & 5 & 1{,}306 & 1{,}403 & 1{,}351 & 5 & 0 & 1 & 1.124 & 1.068 \\ \hline \texttt{hamming} & 6 & 1{,}956 & 1{,}964 & 1{,}958 & 1 & 5 & 5 & 1.008 & 1.002 \\ \hline \texttt{johnson} & 4 & 672 & 672 & 672 & 0 & 4 & 4 & 1.000 & 1.000 \\ \hline \texttt{keller} & 2 & 909 & 921 & 911 & 2 & 0 & 1 & 1.013 & 1.003 \\ \hline \texttt{MANN} & 4 & 3{,}192 & 3{,}202 & 3{,}195 & 3 & 1 & 2 & 1.007 & 1.001 \\ \hline \texttt{p\_hat} & 10 & 5{,}151 & 5{,}187 & 5{,}152 & 9 & 1 & 9 & 1.015 & 1.001 \\ \hline \texttt{san} & 10 & 2{,}573 & 2{,}751 & 2{,}621 & 10 & 0 & 4 & 1.192 & 1.051 \\ \hline \texttt{sanr} & 4 & 1{,}106 & 1{,}115 & 1{,}107 & 4 & 0 & 3 & 1.013 & 1.006 \\ \hline \textbf{All} & \textbf{68} & \textbf{26{,}130} & \textbf{26{,}603} & \textbf{26{,}294} & \textbf{50} & \textbf{18} & \textbf{37} & \textbf{1.192} & \textbf{1.068} \\ \hline \end{tabular} \caption{Part K: total cover sizes by family, number of instances on which \textsc{Salvador} is strictly smaller (``Wins''), optimal instances and largest ratio to the optimum, for Hvala and \textsc{Salvador}.} \label{tab:salvador-hvala} \end{table} \textsc{Salvador} is never worse than Hvala, strictly better on $50$ instances, optimal on $37$ against $18$, with mean ratio $1.0071$ against $1.0253$ and maximum $1.068$ (\texttt{gen400\_p0.9\_75}, $347$ against $325$) against $1.192$; the largest gains are on \texttt{san400\_0.9\_1} ($300$ against $348$), \texttt{san200\_0.9\_1} ($130$ against $155$), \texttt{san200\_0.9\_2} ($140$ against $162$) and \texttt{gen200\_p0.9\_55} ($145$ against $163$), all optimal; the total cover size is $26{,}294$ against $26{,}603$. It cannot be worse by construction (Theorem~\ref{thm:ratio2}), since Hvala's candidates are among its own. The cumulative algorithm time is $190$ seconds against $121$, the slowest instance being \texttt{p\_hat700-1} ($14$ seconds). The two sets of times come from separate runs, so the comparison is indicative only. \subsection{Running time} \label{sec:scaling} The script \texttt{car\_scaling.py} times the whole call on eleven families at $n=1{,}000$, $2{,}000$, $4{,}000$ and $8{,}000$ and fits $\log t$ against $\log(n+m)$ (Table~\ref{tab:scaling}). \begin{table}[!htbp] \centering \scriptsize \setlength{\tabcolsep}{3pt} \resizebox{\textwidth}{!}{% \begin{tabular}{|l|r|r|r|r|r|r|r|r|} \hline \textbf{Family} & \textbf{Max $n$} & \textbf{Max $m$} & \textbf{Slope} & \textbf{$R^2$} & \textbf{$\mu$s$/(n{+}m)$, first} & \textbf{last} & \textbf{Max doubling} & \textbf{Max time (s)} \\ \hline Random 3-regular & 8{,}000 & 12{,}000 & 1.049 & 0.999 & 139 & 154 & 2.14 & 3.08 \\ \hline Random 6-regular & 8{,}000 & 24{,}000 & 1.094 & 1.000 & 123 & 152 & 2.19 & 4.85 \\ \hline Random 12-regular & 8{,}000 & 48{,}000 & 1.074 & 1.000 & 121 & 142 & 2.18 & 7.93 \\ \hline Erd\H{o}s--R\'enyi, avg.\ deg.\ 4 & 7{,}861 & 15{,}934 & 1.080 & 0.998 & 124 & 147 & 2.30 & 3.50 \\ \hline Erd\H{o}s--R\'enyi, avg.\ deg.\ 16 & 8{,}000 & 63{,}718 & 1.030 & 1.000 & 182 & 192 & 2.07 & 13.77 \\ \hline Barab\'asi--Albert, $m=3$ & 8{,}000 & 23{,}991 & 1.371 & 0.977 & 116 & 264 & 3.87 & 8.44 \\ \hline Watts--Strogatz, $k=6$ & 8{,}000 & 24{,}000 & 0.889 & 0.987 & 258 & 212 & 2.27 & 6.77 \\ \hline 2D grid & 7{,}921 & 15{,}664 & 1.056 & 0.997 & 425 & 472 & 2.22 & 11.13 \\ \hline Random tree & 8{,}000 & 7{,}999 & 1.063 & 0.998 & 362 & 415 & 2.27 & 6.64 \\ \hline Random bipartite, avg.\ deg.\ 6 & 7{,}992 & 24{,}000 & 0.857 & 0.952 & 352 & 248 & 2.14 & 7.93 \\ \hline Triangle-free process, avg.\ deg.\ 4 & 7{,}832 & 16{,}000 & 1.060 & 0.999 & 122 & 140 & 2.22 & 3.33 \\ \hline \end{tabular}% } \caption{Running time of \textsc{Salvador} on graphs of doubling size: least-squares slope of $\log t$ against $\log(n+m)$ and its $R^2$ (a linear algorithm has slope $1$), time per element at the smallest and largest size, largest ratio $t(2n)/t(n)$, and time at the largest size.} \label{tab:scaling} \end{table} On eight families the fitted exponent is between $1.03$ and $1.09$ with $R^2\ge0.997$, and every doubling multiplies the time by $1.86$ to $2.30$; over all families the time per element is $116$ to $472$ microseconds. On the Watts--Strogatz and random bipartite families the time per element falls with the size, and the slopes are $0.89$ and $0.86$. On the Barab\'asi--Albert family the last doubling multiplies the time by $3.87$, the largest share of it in $c_{15}$ ($4.3$ of $8.4$ seconds at $n=8{,}000$), whose swap searches stop at a fixed multiple of $n+m$ (Theorem~\ref{thm:runtime}); four sizes over a factor of eight cannot prove an asymptotic exponent, but none of the other ten families shows growth beyond a linear algorithm with Python constant factors. On the small graphs of Part~A the whole algorithm took $2.01$ seconds for $442$ evaluations, of which $1.10$ seconds in $c_{10}$, $0.44$ in $c_{14}$ and $0.37$ in $c_{15}$; the slowest call took $0.09$ seconds. \section{Conclusion} \label{sec:conclusion} \textsc{Salvador} 0.1.4 is a linear-time ensemble for Minimum Vertex Cover with seventeen strategies, the base strategies first and the improvers last. It always returns a valid cover (Theorem~\ref{thm:correctness}) of size at most $2\tau-r$ (Theorem~\ref{thm:twotau}), so its ratio is at most $1.999999999$ on every graph with $\tau\le10^{9}r$, in particular on every graph with at most $10^{9}+1$ vertices, and every strategy runs in $O((n+m)\,\alpha(n))$ time (Theorem~\ref{thm:runtime}). The per-class theorems of Section~\ref{sec:perclass} prove a minimum cover on forests, cycles, complete and complete bipartite graphs and every regular or degree-separated bipartite graph, on every bipartite graph on which the phases of $c_9$ reach a maximum matching, ratio $2-2/(d+1)$ on $d$-regular graphs, $11/6$ on subcubic graphs, and a ratio below $1.999999999$ on every graph outside a residue $\mathcal{R}$ of nearly K\H{o}nig--Egerv\'ary graphs with more than $10^9$ vertices, on which the a-posteriori certificate of Theorem~\ref{thm:posterior} is exact up to a factor $1+5.1\cdot10^{-10}$. The guarantees come from different strategies on different graphs, and so does the quality measured in Section~\ref{sec:suite}. The minimum-degree rules of $c_5$ and $c_8$ give the best independent covers on regular and random graphs, the bipartite solvers of $c_9$ and $c_{10}$ and the reductions of $c_{11}$ make the bipartite graphs exact, and the local searches and reductions of the improvers close most of the remaining gap on the Khot--Regev YES instances. On the $68$ DIMACS clique complements the ensemble is never worse than Hvala and optimal on $37$ instances against $18$. The bound $|C|\le2\tau-|M|$, which would give the ratio $3/2$, held for the returned cover on every instance with a known optimum on which it was tested and was certified on the six without one, while $c_1$ and $c_2$ alone violate it on small graphs. We do not claim that \textsc{Salvador} is a $3/2$-approximation. The bound is a conjecture (Conjecture~\ref{conj:ensemble}); the experiments concern graphs of at most $5{,}000$ vertices in quick mode, most of those with a known optimum are small, 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 can be guaranteed today is the per-instance certificate: whenever $|C|\le\frac32L$ for a computable lower bound $L$, the cover is proved to be within ratio $3/2$ on that graph. Future work includes sharper lower bounds, larger Khot--Regev YES-type instances, and an analysis of the layers of $c_9$ on non-bipartite graphs. The implementation is freely available as the \texttt{Salvador} package on PyPI~\cite{Vega26Salvador}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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{Salvador}, 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/salvador} (release \texttt{v0.1.4}); the experiments of Section~\ref{sec:suite} are reproduced by running the scripts of \texttt{car/} with \texttt{-{}-quick}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{elsarticle-num} \bibliography{biblio} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}