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

We present the Hvala algorithm, a linear-time ensemble approximation method for the Minimum Vertex Cover problem. Hvala combines three complementary heuristics — a maximal-matching 2-approximation, a linear-time maximum-degree greedy implemented via a bucket-queue, and the degree-1 weighted-reduction “Hallelujah heuristic” studied in a companion work — with a redundant-vertex pruning post-processing step, and returns the smallest of the four resulting covers. Theoretical guarantees. We prove rigorously that Hvala achieves worst-case approximation ratio ρ ≤ 2 for every finite, simple, undirected graph: the classical maximal-matching component alone already yields this bound, and the pruning step is shown to preserve cover validity while never increasing cover size. The companion work moreover establishes the strict pointwise inequality |C3| < 2 · OPT(G) on every finite simple graph — the Hallelujah heuristic’s approximation ratio is asymptotic to 2 (strictly less than 2 on each graph, with supremum equal to 2 over all graphs) — and we show that this strict pointwise inequality is inherited by Hvala. Hvala runs in O(n + m) time and O(n + m) space. Empirical performance. We validate Hvala on two independent experimental studies totalling 239 instances. The first uses 109 vertex-cover instances of the public NPBench collection (41 FRB hard instances and 68 DIMACS clique-complement graphs, both with known optima), completed in 126.97 seconds: Hvala attains mean approximation ratio 1.021, with maximum 1.192 on a single Sanchis adversarial instance. The second evaluates Hvala on 130 real-world large graphs from the Network Data Repository (Cai’s undirected simple graph collection), reaching up to 3 million vertices and 15 million edges, completed in approximately 95.5 minutes of cumulative solve time; on the 51 instances with published best-known cover sizes, mean ratio is 1.006 and maximum 1.036. Prospects for a √2 − ϵ bound. Across the combined 160 instances with known optima, every approximation ratio lies below 1.414; 93.8% lie below 1.05 and 96.9% below 1.10. The natural open problem we propose as the continuation of this work is whether there exists a fixed constant ϵ > 0 such that Hvala achieves uniform ratio √2 − ϵ — either on all graphs (which, by SETH-based hardness, would imply P = NP) or, more realistically, on broad but restricted graph classes (bounded degree, bounded clique number, bounded treewidth, or structural families such as power-law and expander-like graphs). We do not prove such a bound here and do not claim one holds on all graphs; what we claim is that the combination of rigorous ≤ 2 guarantee, pointwise strict < 2 inequality, linear time, and observed ratios uniformly below 1.414 makes Hvala a plausible vehicle for such a refined analysis. The algorithm is publicly available via PyPI as the hvala package.