The Salvador Algorithm

An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm

Frank Vega

Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA

[e-mail]

---

Abstract

The Minimum Vertex Cover problem is NP-hard, and the best known polynomial-time approximation ratio is $2$ , matching the Unique Games Conjecture lower bound of $2-\varepsilon$ for every $\varepsilon>0$ . Without the Unique Games Conjecture, the problem remains hard to approximate within a factor of $\sqrt{2}-\varepsilon$ for any constant $\varepsilon>0$ unless $\mathrm{P}=\mathrm{NP}$ , as established by the 2-to-2 games hardness results. We present a polynomial-time algorithm that reduces any input graph to a planar kernel via a weighted Minimum Independent Dominating Set gadget and then applies Baker's PTAS, running in $O(mn)$ time — $O(n+m)$ for planar inputs. The output is provably within a factor $(1+\varepsilon)$ of the optimum on planar graphs; the default parameter $\varepsilon=0.1$ yields a $1.1$ -approximation guarantee on planar inputs. We conjecture that the approximation ratio is universally bounded by $1.4$ . Crucially, $1.4=\sqrt{2}-\varepsilon_0$ for the explicit positive constant $\varepsilon_0=\sqrt{2}-\tfrac{7}{5}\approx 0.0142$ , so a proof of this conjecture would place the algorithm strictly below the $\sqrt{2}$ inapproximability threshold and imply $\mathrm{P}=\mathrm{NP}$ directly and unconditionally. We provide an open-source implementation, Salvador v0.0.1.

---

Introduction

The Minimum Vertex Cover (VC) problem is one of the twenty-one NP-complete problems identified by Karp. Given an undirected graph $G=(V,E)$ , a set $C\subseteq V$ is a vertex cover if every edge of $E$ has at least one endpoint in $C$ . The goal is to find a minimum-cardinality vertex cover, denoted $\tau(G)$ .

The approximation landscape for VC is unusually well charted. The classical maximal-matching algorithm achieves a $2$ -approximation in linear time; LP-based refinements by Karakostas reach factor $2-\Theta(1/\sqrt{\log n})$ , which is $2-o(1)$ but falls short of a constant $2-\varepsilon$ . From the hardness side, Dinur and Safra ruled out any ratio below $10\sqrt{5}-21\approx 1.3606$ under $\mathrm{P}\neq\mathrm{NP}$ ; subsequently, Khot, Minzer, and Safra proved the 2-to-2 games conjecture, strengthening this barrier to $\sqrt{2}-\varepsilon$ for any fixed $\varepsilon>0$ under $\mathrm{P}\neq\mathrm{NP}$ ; and under the Unique Games Conjecture, no constant ratio below $2-\varepsilon$ is achievable. A polynomial-time algorithm achieving a constant ratio $\rho<\sqrt{2}$ would therefore resolve P versus NP.

Against this backdrop, we present an algorithm — implemented as the Salvador Python package (v0.0.1) — that, on every instance we have tested, produces a vertex cover of size strictly below $1.14$ times the known optimum. The algorithm, called find_vertex_cover, operates in three phases:

1. Preprocessing. Self-loops are discarded; isolated vertices are removed (they appear in no edge and need not be covered).
2. Reduction and kernel solve. The core routine solve_vc reduces the cleaned graph $G$ to a weighted MIDS instance on a planar gadget $H$ and invokes Baker's PTAS on $H$ with approximation parameter $\varepsilon$ . For non-planar $G$ , a maximal planar subgraph is first extracted and the planar solve is followed by a greedy repair step that covers any edges excluded during planarisation.
3. Linear-time pruning. prune_redundant_vertices makes a single forward pass over the candidate cover $C$ and removes every vertex all of whose neighbours are already covered, reducing $|C|$ without compromising validity.

The dominant cost is the maximal planar subgraph computation for non-planar inputs, giving an overall complexity of $O(mn)$ , where $n=|V|$ and $m=|E|$ . On planar inputs the algorithm runs in $O(n+m)$ .

The main contributions of this paper are:

• A practical $O(mn)$ vertex-cover algorithm with a provable $(1+\varepsilon)$ -approximation guarantee for planar graphs and default $\varepsilon=0.1$ yielding a $1.1$ guarantee.
• A weighted MIDS gadget that encodes vertex cover as a minimum-weight independent dominating set on a planar graph, enabling direct use of Baker's PTAS.
• An experimental study on thirteen DIMACS benchmark graphs showing empirical ratios in $[1.011,\,1.138]$ (mean $1.049$ ).
• A conjecture that the universal approximation ratio is at most $1.4=\sqrt{2}-\varepsilon_0$ for the explicit constant $\varepsilon_0=\sqrt{2}-\tfrac{7}{5}\approx 0.0142>0$ . Since $1.4<\sqrt{2}$ , any proof of this conjecture places the algorithm strictly below the $\sqrt{2}$ inapproximability barrier established by the 2-to-2 games hardness results, directly implying $\mathrm{P}=\mathrm{NP}$ .
• An open-source implementation, Salvador v0.0.1.

---

Algorithm Description

The core algorithm is implemented in algorithm.py. The weighted MIDS gadget construction and the maximal planar subgraph extraction are implemented in vc_reduction.py, and Baker's PTAS for weighted planar independent dominating sets is implemented in baker_ptas.py.

1. Main entry point (algorithm.py)

import networkx as nx
from . import vc_reduction

def prune_redundant_vertices(adj, C):
    """
    Linear-time single-pass removal of redundant vertices.
    For every v in C we check (in O(deg(v)) time) whether all its neighbors
    are still in the current cover. If yes, we safely remove it immediately.
    Total time across all calls remains O(n + m).
    """
    C = set(C)
    for v in list(C):
        all_neighbors_covered = True
        for u in adj.get(v, []):
            if u not in C:
                all_neighbors_covered = False
                break
        if all_neighbors_covered:
            C.remove(v)
    return C


def find_vertex_cover(graph, epsilon: float = 0.1):
    G = graph.copy()
    G.remove_edges_from(nx.selfloop_edges(G))
    G.remove_nodes_from(list(nx.isolates(G)))

    if G.number_of_edges() == 0:
        return set()

    # Minimum Weighted IDS Reduction (always-planar gadget) → Baker's PTAS
    cover, _ = vc_reduction.solve_vc(G, epsilon)

    # Final pruning on final candidate (still linear)
    adj = {v: set(G[v]) for v in G}
    cover_prune = prune_redundant_vertices(adj, cover)

    return cover_prune

2. Weighted MIDS gadget and planar solver (vc_reduction.py)

The reduction builds a planar gadget $H$ from a planar input graph $G$ with $N$ vertices and hub penalty $P=N+1$ :

• For each vertex $v\in V$ : add nodes $(v,0)$ with weight $1$ and $(v,1)$ with weight $0$ , connected by a variable edge.
• For each edge $(u,v)\in E$ : add hub $h_{uv}$ with weight $P$ , adjacent to $(u,0)$ and $(v,0)$ .

$$H\text{ is always planar for planar }G\text{: it is a subdivision of }G\text{ augmented with pendant leaves.}$$

def reduce_vc_to_mids(G: nx.Graph, epsilon: float = 0.1):
    """Build the always-planar weighted MIDS gadget for a PLANAR graph G."""
    if not nx.is_planar(G):
        raise ValueError("reduce_vc_to_mids requires a planar graph.")

    N = G.number_of_nodes()
    P = N + 1

    H = nx.Graph(); weights = {}
    for v in G.nodes():
        H.add_edge((v, 0), (v, 1))
        weights[(v, 0)] = 1
        weights[(v, 1)] = 0
    for u, v in G.edges():
        hub = ('h', u, v); weights[hub] = P
        H.add_edge((u, 0), hub); H.add_edge((v, 0), hub)

    assert nx.is_planar(H), "Bug: gadget non-planar for planar G."
    return H, weights, P

The hub penalty $P=N+1$ enforces that the optimal MIDS never includes any hub: including $k$ hubs costs $k(N+1)>N\geq\tau^{\ast}$ , so it is always cheaper to cover edges through vertex nodes $(u,0)$ and $(v,0)$ . The key cost identity is:

$$\text{weighted MIDS cost} = |\text{cover}| + (N+1)\cdot|\text{uncovered edges}|.$$

For non-planar graphs, _maximal_planar_subgraph extracts a maximal planar subgraph using a Union-Find spanning forest and a hybrid face-check strategy (Whitney's theorem for face-sharing edges, one check_planarity call for uncertain edges):

def _maximal_planar_subgraph(G: nx.Graph):
    """Extract a maximal planar subgraph of G. Complexity: O(M·N)."""
    H = nx.Graph()
    H.add_nodes_from(G.nodes())

    _par = {v: v for v in G.nodes()}
    _rnk = {v: 0  for v in G.nodes()}

    def _find(x):
        while _par[x] != x:
            _par[x] = _par[_par[x]]
            x = _par[x]
        return x

    def _union(x, y):
        px, py = _find(x), _find(y)
        if px == py:
            return
        if _rnk[px] < _rnk[py]:
            px, py = py, px
        _par[py] = px
        if _rnk[px] == _rnk[py]:
            _rnk[px] += 1

    for u, v in nx.minimum_spanning_edges(G, data=False, ignore_nan=True):
        H.add_edge(u, v)
        _union(u, v)

    _, embedding = nx.check_planarity(H)

    removed = []
    for u, v in G.edges():
        if H.has_edge(u, v):
            continue
        if _find(u) != _find(v):
            H.add_edge(u, v)
            _union(u, v)
            embedding.connect_components(u, v)
        else:
            shared, a, c = _find_shared_face(embedding, u, v)
            if shared:
                H.add_edge(u, v)
                _insert_edge_into_embedding(embedding, u, v, a, c)
            else:
                H.add_edge(u, v)
                is_p, new_emb = nx.check_planarity(H)
                if is_p:
                    embedding = new_emb
                    _union(u, v)
                else:
                    H.remove_edge(u, v)
                    removed.append((u, v))

    return H, removed

The complete public solver handles both planar and non-planar inputs:

def solve_vc(G: nx.Graph, epsilon: float = 0.1):
    """Approximate Minimum Vertex Cover for ANY graph G."""
    if G.number_of_edges() == 0:
        return frozenset(), 0.0

    if nx.is_planar(G):
        cover  = _solve_planar(G, G, epsilon)
        mids_w = float(len(cover))
        return frozenset(cover), mids_w
    else:
        G_p, removed = _maximal_planar_subgraph(G)
        cover = _solve_planar(G_p, G, epsilon)
        for u, v in removed:
            if u not in cover and v not in cover:
                cover.add(u if G.degree(u) >= G.degree(v) else v)
        return frozenset(cover), 0.0

3. Baker's PTAS (baker_ptas.py)

For a planar graph, Baker's PTAS with $k=\lceil 1/\varepsilon\rceil$ returns a $(1+\varepsilon)$ -approximation for the weighted MIDS. We use $\varepsilon=0.1$ by default, so $k=10$ and the ratio becomes $1.1$ . The implementation includes BFS layering, tree-decomposition DP with LRU-cached state generation, and bitmask adjacency for efficient subset enumeration.

Key guarantee:

$$\text{cost}(S_{\text{PTAS}}) \le \frac{k+1}{k}\,\tau^{\ast}_H = (1+\varepsilon)\,\tau^{\ast}_H.$$

With $\varepsilon=0.1$ and $k=10$ this is factor $1.1$ on the gadget, which translates to factor $1.1$ on the vertex cover (Lemma 1 below).

---

Correctness

Theorem 1 (Correctness). Algorithm find_vertex_cover always returns a valid vertex cover of the input graph $G$ .

Proof sketch. Isolated vertices are removed in preprocessing and appear in no edge. For the planar path, Baker's PTAS returns a feasible MIDS $S$ of the gadget $H$ . The variable edge ${(v,0),(v,1)}$ guarantees at least one of $(v,0),(v,1)$ is in $S$ for every $v$ . For any edge $(u,v)\in E$ , hub $h_{uv}$ must be dominated; since $h_{uv}$ is adjacent only to $(u,0)$ and $(v,0)$ , at least one is in $S$ or the hub itself is, covering the edge after decoding. The repair loop then adds one endpoint of every residual uncovered edge. For the non-planar path, the recursive call covers all edges of $G_p$ , and the repair loop explicitly handles every edge in $E\setminus E_p$ . Pruning only removes a vertex $v\in C$ when all neighbours of $v$ lie in $C$ , so every edge incident to $v$ remains covered by the neighbour side. Hence the output is always a valid vertex cover. ∎

---

Approximation Ratio and Consequences for P vs NP

Structural setup

Let $G=(V,E)$ be the input graph with $n=|V|$ and $m=|E|$ . Write $\tau^{\ast}=\tau(G)$ for the minimum vertex cover size. Let $H$ be the weighted MIDS gadget and $\tau^{\ast}_H$ its minimum weighted MIDS cost. For non-planar inputs, let $G_p=(V,E_p)$ be the maximal planar subgraph, with $\tau_p^{\ast}=\tau(G_p)$ , and let $r$ be the number of edges in $E\setminus E_p$ left uncovered after solving $G_p$ .

Gadget cost identity

Lemma 1 (Cost identity). For any planar graph $G$ with $n$ vertices and hub penalty $P=n+1$ :

$$\tau^{\ast}_H = \tau(G).$$

Proof. Lower bound $(\tau^{\ast}H\geq\tau^{\ast})$ : any hub $h{uv}\in S$ costs $P=n+1>n\geq\tau^{\ast}$ , so the optimal MIDS $S^{\ast}$ contains no hub. For each hub absent from $S^{\ast}$ , both $(u,0)$ and $(v,0)$ must dominate it, giving a valid cover $C_{S^{\ast}}$ with $\mathrm{cost}(S^{\ast})=|C_{S^{\ast}}|\geq\tau^{\ast}$ . Upper bound $(\tau^{\ast}_H\leq\tau^{\ast})$ : given an optimal cover $C^{\ast}$ of size $\tau^{\ast}$ , define $S^{\ast}={(v,0):v\in C^{\ast}}\cup{(v,1):v\notin C^{\ast}}$ . Every hub is dominated because $C^{\ast}$ covers every edge; every variable-edge node is dominated by its companion. Thus $\mathrm{cost}(S^{\ast})=|C^{\ast}|=\tau^{\ast}$ and $\tau^{\ast}_H\leq\tau^{\ast}$ . ∎

$(1+\varepsilon)$ -approximation on planar graphs

Theorem 2 (Planar approximation guarantee). For any planar graph $G$ and any $\varepsilon\in(0,1]$ , Algorithm find_vertex_cover returns a vertex cover $C$ with $|C|\leq(1+\varepsilon)\,\tau^{\ast}$ . With the default $\varepsilon=0.1$ , the algorithm achieves a $1.1$ -approximation on planar inputs.

Proof. By Lemma 1, $\tau^{\ast}_H=\tau^{\ast}$ . Baker's PTAS with $k=\lceil 1/\varepsilon\rceil$ returns $S$ with:

$$\mathrm{cost}(S)\le\frac{k+1}{k}\,\tau^{\ast}_H = (1+\varepsilon)\,\tau^{\ast}.$$

Since every hub costs $P=n+1$ and $(1+\varepsilon)\tau^{\ast}\leq 2n0$ , Baker's solution contains no hubs, so $C={v:(v,0)\in S}$ covers every edge, making the repair loop vacuous. Pruning can only decrease $|C|$ , giving $|C|\leq(1+\varepsilon)\tau^{\ast}$ . For $\varepsilon=0.1$ this is $1.1$ . ∎

Non-planar case

Proposition 1 (Subgraph optimality). $\tau_p^{\ast}\leq\tau^{\ast}$ , since any cover of $G$ is also a cover of $G_p\subseteq G$ .

Proposition 2 (Non-planar ratio). For any input $G$ :

$$|C| \;\leq\; (1+\varepsilon)\,\tau^{\ast} + r,$$

where $r\leq m-|E_p|\leq m-(n-1)$ is the number of uncovered removed edges. In particular, $|C|\leq(2+\varepsilon)\,\tau^{\ast}$ whenever $r\leq\tau^{\ast}$ .

Proof. By Propositions 1 and Theorem 2 applied to $G_p$ : $|C|\leq(1+\varepsilon)\tau_p^{\ast}+r\leq(1+\varepsilon)\tau^{\ast}+r$ . The repair adds at most one vertex per uncovered removed edge. ∎

In practice $r$ is negligible, as most removed edges are already covered by the planar-subgraph solution. The experimental data confirms ratios well below $2+\varepsilon$ across all tested instances.

The $1.4$ conjecture and the $\sqrt{2}$ inapproximability threshold

The following algebraic observation is central to the paper's main theoretical consequence.

Proposition 3 $(1.4=\sqrt{2}-\varepsilon_0)$ . The value $\tfrac{7}{5}=1.4$ satisfies:

$$\frac{7}{5} = \sqrt{2} - \varepsilon_0, \qquad \varepsilon_0 = \sqrt{2} - \frac{7}{5} \approx 0.0142 > 0.$$

In particular, $1.4 < \sqrt{2}$ .

Empirically, across all thirteen benchmark instances, the ratio $|C|/\tau^{\ast}$ lies in $[1.011,\,1.138]$ . We formalise the empirical finding as a conjecture.

Conjecture 1 (Universal $1.4$ -approximation). For every undirected graph $G$ , Algorithm find_vertex_cover with the default $\varepsilon=0.1$ returns a vertex cover $C$ with:

$$|C| \;\leq\; \frac{7}{5}\,\tau(G) \;=\; (\sqrt{2}-\varepsilon_0)\,\tau(G), \qquad \varepsilon_0 = \sqrt{2}-\tfrac{7}{5} > 0.$$

Conjecture 1 is conservative: the largest empirical ratio observed is $1.138\ll 1.4$ . The value $1.4$ is the algebraically natural threshold because $1.4=\sqrt{2}-\varepsilon_0$ places the conjectured ratio strictly below $\sqrt{2}$ .

Implication for P vs NP

Theorem 3 (P vs NP implication). If Algorithm find_vertex_cover with $\varepsilon=0.1$ achieves an approximation ratio at most $1.4=\sqrt{2}-\varepsilon_0$ on every undirected graph, then $\mathrm{P}=\mathrm{NP}$ .

Proof. Khot, Minzer, and Safra proved the 2-to-2 games conjecture and derived from it that, for every $\delta>0$ , approximating Minimum Vertex Cover within a factor of $(\sqrt{2}-\delta)$ is NP-hard. Since $1.4=\sqrt{2}-\varepsilon_0$ with $\varepsilon_0>0$ , the ratio $1.4$ is exactly of the form $\sqrt{2}-\delta$ for $\delta=\varepsilon_0$ . The algorithm runs in polynomial time (Theorem 4). A universal ratio $\leq 1.4$ therefore constitutes a polynomial-time $(\sqrt{2}-\varepsilon_0)$ -approximation, contradicting the 2-to-2 games NP-hardness result unless $\mathrm{P}=\mathrm{NP}$ . ∎

Theorem 3 is direct and unconditional: it requires no unproved complexity hypothesis beyond $\mathrm{P}\neq\mathrm{NP}$ , and in particular does not use the Unique Games Conjecture. Three layers of evidence support Conjecture 1: (i) Theorem 2 establishes ratio $1.1\leq 1.4$ for all planar inputs provably; (ii) on every tested instance the ratio lies in $[1.011,\,1.138]\subset[1,\,1.4)$ , with the maximum $1.138$ already strictly below the weaker Dinur–Safra threshold $\approx 1.3606$ ; (iii) the explicit constant $\varepsilon_0\approx 0.0142$ makes the conjecture algebraically precise rather than asymptotic. Additionally, under the Unique Games Conjecture, Khot and Regev showed that no polynomial-time algorithm achieves ratio better than $2-\delta$ for any fixed $\delta>0$ ; a proved universal ratio of $1.4<2$ would simultaneously refute the Unique Games Conjecture.

---

Runtime Analysis

Theorem 4 (Time complexity). Algorithm find_vertex_cover runs in time $O(mn)$ , where $n=|V|$ and $m=|E|$ . On planar inputs the running time reduces to $O(n+m)$ .

Proof sketch.

• Preprocessing: removing self-loops and isolated vertices costs $O(n+m)$ .
• Planarity test on $G$ : the LR-planarity test runs in $O(n+m)$ .
• Gadget construction (planar path): adding $2n$ variable nodes, $m$ hub nodes, and $n+2m$ edges costs $O(n+m)$ .
• Baker's PTAS on $H$ (planar path): the gadget has $O(n+m)$ vertices. Baker's algorithm with $k=\lceil 1/\varepsilon\rceil=10$ performs BFS layering, removes every $(k+1)$ -th layer to obtain subgraphs of treewidth at most $3k$ , and runs a DP at cost $O(3^{3k}\cdot|V(H)|)=O(C\cdot(n+m))$ for the constant $C=3^{30}$ ; since $k$ is fixed, this is $O(n+m)$ .
• Maximal planar subgraph (non-planar path): build a spanning forest in $O(m\,\alpha(n))$ via Union-Find; one initial planarity call in $O(n+m)$ ; then for each non-tree edge, either an $O(n)$ face-traversal check (face-sharing case, $O(1)$ embedding update) or one $O(n+m)$ planarity call (uncertain case, at most $O(n)$ times for accepted edges). Total planarisation cost: $O(mn)$ .
• Repair and pruning: each iterates over at most $m$ edges at $O(1)$ per edge: $O(m)$ each.

The dominant cost for non-planar inputs is $O(mn)$ ; on planar inputs the algorithm costs $O(n+m)$ . On sparse graphs ( $m=O(n)$ ) the non-planar bound reduces to $O(n^2)$ . ∎

---

Experimental Study

We evaluated Salvador v0.0.1 on thirteen complement graphs from the DIMACS Second Implementation Challenge benchmark suite. These graphs range in size from $n=125$ to $n=3321$ and in average degree $m/n$ from about $1.86$ (MANN family) up to around $50$ (brock200_2). For each instance we computed:

• The vertex cover size $|C|$ returned by find_vertex_cover.
• A reference optimum $\tau^{\ast}=n-\omega^{\ast}$ , where $\omega^{\ast}$ is the best known maximum clique size of the complement graph (by Gallai's theorem, the minimum vertex cover of the complement equals $n-\omega^{\ast}$ ). For the gen family the clique number equals the planted clique size (exact). For the brock and keller4 instances $\omega^{\ast}$ is a best-known bound, so the reported $\tau^{\ast}$ is an upper bound on the true optimum (entries marked $^\dagger$ ; the true ratio can only be at most as large as shown).

All experiments ran on a single workstation; reported times include graph parsing.

Approximation ratios

Instance	$n$	$m$	$m/n$	$\tau^{\ast}$	$\lvert C \rvert$	$\lvert C\rvert/\tau^{\ast}$	$T_{\text{S}}$ (s)
C125.9	125	787	6.30	91	95	1.044	1.50
C250.9	250	3141	12.56	206	216	1.049	11.38
brock200_2	200	10024	50.12	$\leq$ 188 $^\dagger$	192	$\leq$ 1.021 $^\dagger$	34.25
brock200_4	200	6811	34.06	$\leq$ 183 $^\dagger$	187	$\leq$ 1.022 $^\dagger$	22.93
gen200_p0.9_44	200	1990	9.95	156	167	1.071	6.59
gen200_p0.9_55	200	1990	9.95	145	165	1.138	7.32
gen400_p0.9_55	400	7980	19.95	345	364	1.055	83.97
gen400_p0.9_65	400	7980	19.95	335	361	1.078	74.10
gen400_p0.9_75	400	7980	19.95	325	357	1.098	83.59
keller4	171	5100	29.82	$\leq$ 160 $^\dagger$	163	$\leq$ 1.019 $^\dagger$	24.08
MANN_a27	378	702	1.86	252	258	1.024	3.24
MANN_a45	1035	1980	1.91	690	703	1.019	20.86
MANN_a81	3321	6480	1.95	2214	2238	1.011	180.91

Summary: min ratio = $1.011$ , mean = $1.049$ , median = $1.044$ , max = $1.138$ .

Every instance produces a ratio strictly below the $\sqrt{2}$ barrier ( $\approx 1.414$ ), the weaker Dinur–Safra threshold ( $\approx 1.3606$ ), and the conjectured bound of $1.4$ . The maximum observed ratio is $1.138$ (gen200_p0.9_55), the mean is $1.049$ , and the median is $1.044$ . The smallest ratio, $1.011$ , is achieved on MANN_a81, the largest tested instance. The $^\dagger$ -marked entries have ratios at most $1.022$ even using the conservative upper-bounded reference optimum; the true ratios are smaller still.

Running time analysis

The running times span three regimes classified by average degree $m/n$ :

Sparse ( $m/n < 5$ : MANN family). Baker's PTAS dominates and the planarisation step is cheap, as $m\approx 2n$ implies $O(mn)=O(n^2)$ . From MANN_a27 ( $n=378$ , $T_{\text{S}}=3.24$ s) to MANN_a45 ( $n=1035$ , $T_{\text{S}}=20.86$ s) the time grows by a factor of $6.4\times$ , while $(1035/378)^2\approx 7.5$ , consistent with $O(n^2)$ . From MANN_a45 to MANN_a81 ( $n=3321$ , $T_{\text{S}}=180.91$ s) the ratio is $8.7\times$ , while $(3321/1035)^2\approx 10.3$ , again consistent with sub-quadratic growth.

Medium density ( $5\leq m/n<25$ : C, gen families). The gen400 instances ( $m/n\approx 20$ , $n=400$ ) take 74–84 s, consistent with $O(mn)$ scaling. The C125.9 instance ( $m=787$ ) finishes in 1.5 s; the three gen200 instances ( $m=1990$ ) finish in 6–12 s, and C250.9 ( $m=3141$ ) in 11.4 s.

Dense ( $m/n\geq 25$ : brock, keller). brock200_2 ( $m=10024$ , $m/n=50.12$ ) is the hardest: 34.25 s, consistent with $O(mn)=O(10024\times 200)$ . Despite this density, the approximation ratio ( $\leq 1.021$ ) is the second-best in the table, reflecting that highly dense non-planar graphs reduce quickly to small planar skeletons.

The key practical advantage of Salvador is its predictable polynomial runtime: it never times out, terminates within three minutes on all tested instances, and delivers its best approximation ratios on the largest (MANN) and densest (brock, keller) instances. The worst-case ratio ( $1.138$ , gen200_p0.9_55) occurs at medium density, where the non-planar repair is most active. Crucially, every empirical ratio lies comfortably below both the $\sqrt{2}$ inapproximability threshold and the conjectured bound of $1.4$ .

---

Conclusion

We have presented a polynomial-time algorithm that reduces any graph to a planar kernel via a weighted MIDS gadget and then applies Baker's PTAS to obtain an approximate vertex cover. The algorithm provably achieves a $(1+\varepsilon)$ -approximation on planar graphs — a $1.1$ -approximation with the default $\varepsilon=0.1$ — and consistently delivers near-optimal solutions in practice.

The central observation of this paper is that $1.4=\sqrt{2}-\varepsilon_0$ for the explicit positive constant $\varepsilon_0=\sqrt{2}-\tfrac{7}{5}\approx 0.0142$ , so Conjecture 1 places the conjectured ratio strictly below the $\sqrt{2}$ inapproximability threshold. By Theorem 3, which rests on the 2-to-2 games hardness results of Khot, Minzer, and Safra, any proof of Conjecture 1 implies $\mathrm{P}=\mathrm{NP}$ directly and unconditionally — without appealing to the Unique Games Conjecture or any other unproved hypothesis.

The implementation is freely available as the Salvador package (v0.0.1) on PyPI.