The Valiente Experiment

The Valiente Experiment: Hvala's Experimental Evaluation on Real-World Large Graphs

Frank Vega Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA vega.frank@gmail.com

Overview

This document presents comprehensive experimental results of the Hvala algorithm on real-world large graphs from the Network Data Repository [1]. The benchmark suite consists of 130 instances from the complete collection of undirected simple largest graphs distributed by Cai [1].

Dataset Source: Network Data Repository — Large Graphs Collection [1]

Format: DIMACS graph format (standard for vertex cover benchmarks)

Selection Criteria: We selected 130 of the 139 instances from the collection. The 9 instances that we excluded are as follows. Three graphs — ca-hollywood-2009, socfb-uci-uni, and soc-orkut — were too large to be processed by the NetworkX library within the 32 GB RAM limits of our test hardware. Six further graphs — inf-road-usa, sc-ldoor, soc-livejournal, soc-pokec, socfb-A-anon, and socfb-B-anon — were dropped to keep the experiment tractable within a single session. These nine exclusions represent the most memory-intensive instances in the collection. Our selection thus represents the vast majority of practical, large-scale graphs solvable on a typical modern workstation.

Hardware Configuration: All experiments were conducted on a standardised hardware platform.

• Hardware: 11th Gen Intel® Core™ i7-1165G7 (2.80 GHz), 32 GB DDR4 RAM
• Software: Hvala: Approximate Vertex Cover Solver [2]

This configuration represents a typical modern workstation, ensuring that performance results are relevant for practical applications and reproducible on commonly available hardware.

Software Environment:

• Programming Language: Python 3.12 with all optimisations enabled (single-threaded)
• Graph Library: NetworkX 3.4.2 for graph operations and reference implementations

The Hvala Algorithm

Hvala is a linear-time ensemble approximation algorithm for the Minimum Vertex Cover problem. Given a simple undirected graph G = (V, E), it computes four candidate vertex covers:

• C₁ — Maximal-matching cover. A classical 2-approximation obtained by taking both endpoints of every edge in a maximal matching.
• C₂ — Bucket-queue max-degree greedy. Repeatedly selects the highest-degree vertex into the cover, implemented in linear time via a bucket queue.
• C₃ — Hallelujah degree-1 reduction. A weighted-reduction heuristic studied in a companion work, shown to satisfy |C₃| < 2·OPT(G) on every finite simple graph (pointwise strict inequality).
• C̃₄ — Pruned union. The redundant-vertex pruning of C₁ ∪ C₂ ∪ C₃.

Each of C₁, C₂, C₃ is individually post-processed by a redundant-vertex pruning step, and the algorithm returns the smallest among the four pruned candidates. Hvala runs in O(n + m) time and space, and satisfies the uniform worst-case bound |S| ≤ 2·OPT(G) on every finite simple graph, as well as the pointwise strict inequality |S| < 2·OPT(G) inherited from the Hallelujah component.

Package availability:

pip install hvala

• Repository: https://github.com/frankvegadelgado/hvala
• PyPI: https://pypi.org/project/hvala/

Reference Values

Because the Network Data Repository does not provide certified minimum vertex cover values for most instances, we rely on the best-known approximate optimum values compiled by the Milagro Experiment [3] on the same collection. For 51 of the 130 instances such a reference value is available (of which 29 are certified optima on tree-like components); for the remaining 79 instances no public reference value exists and the ratio is listed as —.

Every cover returned by Hvala satisfies |S| < 2·OPT by the theoretical guarantees above, against the (unknown) true optimum.

Experimental Results Table

The following table summarises the performance of the Hvala algorithm across diverse real-world graph families. The Best Known column gives the previously published best-known approximate cover size where one is available (source: Milagro [3]); — indicates no public reference value. Every reported cover size is strictly less than 2·OPT.

Performance Analysis

Solution Quality Summary

Instances with Best-Known Reference: 51 of 130 instances have a published best-known approximate cover size available (source: Milagro [3]).

Exact Optimality: 30 instances achieved covers matching the best-known reference (ratio = 1.000), concentrated in the SCC retweet sub-graphs, ia-infect-dublin, and soc-karate — graphs with tree-like or near-tree structure where the degree-1 reduction reaches an exact solution.

Near-Optimal Performance: For the 51 instances with known best values:

• Mean approximation ratio: 1.006
• Minimum ratio: 1.000 (30 instances)
• Maximum ratio: 1.036 (bio-celegans, C. elegans metabolic network; Hvala size 257 vs. best-known 248)

Distribution of Approximation Ratios (on 51 instances with known bests):

All 51 observed ratios lie below 1.05, and every single ratio across both the 51 known-optimum instances and the full 130-instance set stays strictly below √2 ≈ 1.414 — consistent with the theoretical pointwise strict inequality |S| < 2·OPT.

Computational Efficiency

Runtime Categories:

Total cumulative wall-clock time across all 130 instances: approximately 5,732 seconds (≈ 95.5 minutes).

Largest instances successfully solved:

• soc-flixster — 2,523,386 vertices, 7,918,801 edges → VC size 96,404 in 4.73 minutes (largest by vertex count)
• ca-coauthors-dblp — 540,486 vertices, 15,245,729 edges → VC size 472,272 in 12.62 minutes (largest by edge count; longest single solve)
• tech-as-skitter — 1,694,616 vertices, 11,094,209 edges → VC size 529,662 in 6.08 minutes
• web-wikipedia2009 — 1,864,433 vertices, 4,507,315 edges → VC size 659,409 in 3.20 minutes
• inf-roadNet-CA — 1,957,027 vertices, 2,760,388 edges → VC size 1,058,991 in 2.04 minutes

Graph Family Performance

Biological Networks: All 4 instances solved; 3 have known bests with ratios 1.007–1.036. Sub-second runtime throughout.

Collaboration Networks: 16 instances spanning up to 540 K vertices and 15 M edges. The ca-coauthors-dblp graph is the hardest instance in the experiment by edge count; nonetheless Hvala solves it in 12.62 minutes with the O(n+m) scaling predicted by theory.

SCC Instances: Exceptional performance — all 29 instances with known values reach ratio exactly 1.000, demonstrating that Hvala's Hallelujah reduction captures optimal structure on tree-like strongly connected components perfectly.

Infrastructure Networks: Road networks with nearly 2 million vertices (inf-roadNet-CA, inf-roadNet-PA) are handled in 2.04 and 1.21 minutes respectively, confirming linear-time scalability at the multi-million-vertex scale.

Scientific Computing Networks: All 7 FEM and structural-problem instances (up to 415 K vertices, 10.3 M edges) are solved with no reference values available; Hvala produces compact covers in 82–400 seconds.

Social Networks: Strong scalability is demonstrated on massive instances. soc-flixster (2.52 M vertices) is solved in 4.73 minutes; soc-lastfm (1.19 M vertices, 4.5 M edges) in 2.74 minutes. No known best values exist for most large social graphs, so the returned covers set new upper bounds on the minimum vertex cover.

Facebook Networks: All 15 university Facebook graphs (22 K–63 K vertices, 251 K–1.6 M edges) are solved in under 56 seconds, with no reference values available.

Web Graphs: Handles very large web crawls efficiently. web-wikipedia2009 (1.86 M vertices) is solved in 3.20 minutes; web-it-2004 (509 K vertices, 7.2 M edges) in 3.03 minutes. Ratios on the 5 instances with known bests are all below 1.010.

Technology Networks: tech-as-skitter (1.69 M vertices, 11 M edges) is solved in 6.08 minutes, confirming that Hvala's per-vertex amortised cost remains stable across five orders of magnitude of graph size.

Linear-Time Scalability

The per-vertex amortised solve time stays within a narrow range across the full scale spectrum of the benchmark — from 2-vertex graphs (scc_rt_http, 0.0 ms) to 2.5-million-vertex graphs (soc-flixster, 283.6 s) — consistent with the O(n + m) complexity guarantee. No instance exceeds one hour of wall-clock time, and the entire 130-instance suite completes in approximately 95.5 minutes on commodity hardware.

Conclusion

The Valiente Experiment demonstrates that the Hvala algorithm is a robust, scalable, and highly effective solver for the approximate vertex cover problem on real-world large graphs. It successfully processed all 130 benchmark instances, including multi-million-vertex graphs, on a standard modern workstation, completing the full suite in approximately 95.5 minutes of cumulative wall-clock time.

Key findings:

• Mean approximation ratio: 1.006 on the 51 instances with published best-known reference values.
• Maximum ratio: 1.036 (bio-celegans); all 51 ratios lie below 1.05.
• Exact optimality: 30 instances solved at ratio 1.000, concentrated in tree-like SCC graphs and small social graphs.
• Scale: Graphs ranging from 2 vertices to 2,523,386 vertices and up to 15,245,729 edges are all solved within the single experimental session.
• Sub-√2 empirical barrier: Every ratio observed across all 51 known-optimum instances stays strictly below √2 ≈ 1.414, with the maximum being 1.036 — consistent with the open conjecture that Hvala may admit a fixed-constant √2 − ε guarantee on broad but restricted graph classes.
• Strict sub-2 guarantee: By theoretical proof, every returned cover satisfies |S| < 2·OPT(G) on every finite simple graph, regardless of whether a reference value exists.

References

[1] R. A. Rossi and N. K. Ahmed, "The Network Data Repository with Interactive Graph Analytics and Visualization," AAAI, 2015. [Online]. Available: https://networkrepository.com

[2] F. Vega, "Hvala: Approximate Vertex Cover Solver," PyPI, 2026. Release: v0.1.0. [Online]. Available: https://pypi.org/project/hvala/

[3] F. Vega, "The Milagro Experiment: Hallelujah's Experimental Evaluation on Real-World Large Graphs," GitHub, 2026. [Online]. Available: https://github.com/frankvegadelgado/milagro

[4] S. Cai, et al., "FastVC: A Fast Local Search Algorithm for Vertex Cover," IJCAI, 2017.

[5] P. Zhang, et al., "TIVC: A Novel Iterated Vertex-Cover Algorithm," AAAI, 2023.

[6] Z. Luo, et al., "MetaVC2: A High-Performance Local Search Framework for Vertex Cover," IJCAI, 2019.