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

The Minimum Vertex Cover problem, a cornerstone of NP-hard optimization, has long been bounded by approximation hardness thresholds, including the Unique Games Conjecture's assertion that no polynomial-time algorithm can achieve a ratio better than \( 2 - \epsilon \) for any \( \epsilon > 0 \). This paper introduces a novel reduction-based algorithm that computes a vertex cover with an approximation ratio strictly less than 2 for any finite undirected graph with at least one edge, thereby disproving the Unique Games Conjecture. The approach transforms the input graph into an auxiliary graph with maximum degree 1 using degree-weighted auxiliary vertices, solves the minimum weighted vertex cover optimally in linear time, and projects the solution back to yield a valid cover. We provide a rigorous correctness proof, demonstrating that the projection preserves coverage while exploiting structural slack in finite graphs to ensure the strict sub-2 ratio. Runtime analysis confirms \( O(|V| + |E|) \) efficiency, making the algorithm practical for large-scale instances. This breakthrough not only advances approximation techniques for vertex cover but also resolves a major open question in complexity theory, opening avenues for revisiting UGC-dependent hardness results in other optimization domains.