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

Source abstract

The Minimum Vertex Cover problem is NP-hard. Its classical polynomial-time approximation ratio is 2, and Khot and Regev showed that, assuming the Unique Games Conjecture (UGC), no polynomial-time algorithm can achieve a factor 2 − ε for any fixed ε > 0. We present FINDVERTEXCOVER, an algorithm that reduces any graph to a linear-size planar forest core via a weighted Minimum Independent Dominating Set (MIDS) gadget and solves that gadget with an accuracy-controlled Baker-style PTAS whose layering width is k = ⌈1/ε⌉; non-core edges are then covered by a greedy repair step and a final redundancy-pruning p ass. For any fixed ε the algorithm runs in near-linear time and always returns a valid vertex cover. We include a reproducible experiment, stored in the car/ folder, that computes exact optima without MILP through a branch-and-bound maximum-independent-set solver, with K˝onig/maximum-matching certificates on bipartite i nstances. Under the default call ε = 0.1, across 1,718 feasible graphs—the graph atlas through seven vertices, random and structured bipartite families, grids, and random general graphs—every returned cover is valid and the maximum ratio is 7/4 = 2 − 1/4, attained by an explicit eleven-vertex bipartite graph; no instance exceeds 7/4. We therefore conjecture a universal 7/4 approximation ratio, a bound that the experiment shows is tight. If this 7/4 bound were proved, then, under the standard assumption P ≠ NP, the Khot–Regev UGC-based hardness theorem for Vertex Cover would force the Unique Games Conjecture to be false. An open-source implementation is released as the Salvador package (v0.0.6).