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

Read the full article See related articles

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.
Log in to save this article

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.

Article activity feed