An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm
Discuss this preprint
Start a discussion What are Sciety discussions?Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
The Minimum Vertex Cover (MVC) problem is a fundamental NP-complete problem in graph theory that seeks the smallest set of vertices covering all edges in an undirected graph $G = (V, E)$. This paper presents the \texttt{find\_vertex\_cover} algorithm, an innovative approximation method that transforms the problem to maximum degree-1 instances via auxiliary vertices. The algorithm computes solutions using weighted dominating sets and vertex covers on reduced graphs, enhanced by ensemble heuristics including maximum-degree greedy and minimum-to-minimum strategies. Our approach guarantees an approximation ratio strictly less than $\sqrt{2} \approx 1.414$, which would contradict known hardness results unless P = NP. This theoretical implication represents a significant advancement beyond classical approximation bounds. The algorithm operates in $\mathcal{O}(m \log n)$ time for $n$ vertices and $m$ edges, employing component-wise processing and linear-space reductions for efficiency. Implemented in Python as the Hvala package, it demonstrates excellent performance on sparse and scale-free networks, with profound implications for complexity theory. The achievement of a sub-$\sqrt{2}$ approximation ratio, if validated, would resolve the P versus NP problem in the affirmative. This work enables near-optimal solutions for applications in network design, scheduling, and bioinformatics while challenging fundamental assumptions in computational complexity.