A Breakthrough in Graph Optimization: Solving the Minimum Vertex Cover Problem
Frank Vega · HAL (Le Centre pour la Communication Scientifique Directe) · 2025
We present a polynomial-time algorithm for the Minimum Vertex Cover (MVC) problem in undirected graphs. By reducing MVC to the Minimum Dominating Set (MDS) problem in chordal graphs, we leverage the linear-time solvability of MDS using perfect elimination orderings. Our method transforms the input graph into a chordal graph via a structured encoding, ensuring the MDS of the transformed graph corresponds precisely to the MVC of the original. We prove the algorithm's correctness, guaranteeing a valid and minimal vertex cover. The algorithm handles edge cases efficiently and runs in $O(|V|^2)$ time, advancing MVC solutions and offering insights into graph structure and algorithmic design. This work bridges theoretical graph theory with practical applications and provides strong evidence that P = NP.