Disproving the Unique Games Conjecture

The Vertex Cover Problem, a fundamental NP-complete challenge, seeks the smallest set of vertices in an undirected graph $G = (V, E)$ that covers all edges. This paper presents the \texttt{find\_vertex\_cover} algorithm, an approximation method that partitions $E$ into two claw-free subgraphs using the Burr-Erd\H{o}s-Lov\'asz (1976) approach, computes exact vertex covers for each via the Faenza, Oriolo, and Stauffer (2011) technique in $\mathcal{O}(n^3)$ time, and recursively refines the solution on residual edges. With a worst-case runtime of $ \mathcal{O}(n^4)$, where $n = |V|$, the algorithm achieves an approximation ratio less than 2, surpassing the standard 2-approximation. Implemented in Python, this method leverages efficient triangle detection to enhance performance in claw-free settings, potentially impacting fine-grained complexity conjectures like the Unique Games Conjecture if validated across diverse graph classes. Practically, it aids applications in network design, scheduling, and bioinformatics by providing near-optimal solutions. This work bridges theoretical advancements and practical utility, offering a promising heuristic for vertex cover approximation.