New Insights and Developments on the Vertex Cover Problem
Frank Vega · 2025
We introduce a novel polynomial-time algorithm for solving the Minimum Vertex Cover (MVC) problem in undirected graphs. Our approach reduces the MVC problem to the Minimum Dominating Set (MDS) problem in chordal graphs, exploiting the linear-time solvability of MDS in such graphs using perfect elimination orderings. The algorithm transforms the input graph into a chordal graph through a structured encoding, ensuring that the MDS of the transformed graph corresponds precisely to the MVC of the original graph. We provide a rigorous proof of correctness, demonstrating that the extracted solution is both a valid vertex cover and minimal in size. The algorithm handles edge cases, such as empty graphs and isolated nodes, efficiently and guarantees an exact solution in O(|V|^2) time. This work advances the state of the art in solving the MVC problem and offers new insights into the relationship between graph structure and algorithmic design. Experimental results and theoretical analysis confirm the algorithm's effectiveness, making it a practical and theoretically sound tool for graph optimization tasks. This contribution bridges the gap between theoretical graph theory and practical algorithmic applications, providing a scalable solution for real-world problems. This work also provides strong evidence that P = NP.