💻 computer science

A Reproducible Benchmark Dataset and Experimental Evaluation for the Minimum s-Club Cover Problem

This paper addresses the lack of standardized resources for the Minimum s-Club Cover problem by introducing a fully reproducible benchmark suite comprising 30 diverse graph instances, 4,800 verified optimization runs across eight algorithms, and comprehensive open-access data to facilitate rigorous comparative evaluation and open science.

Original author: Mạnh Đạt

Published 2026-11-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original author: Mạnh Đạt

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast, invisible architecture of our world, connections matter more than the things they connect. Whether it is friends sharing a secret, proteins binding to keep a cell alive, or routers passing data across the internet, these systems are defined by how tightly their parts hold together. Scientists have long sought a way to map these tight-knit groups, looking for clusters where everyone is close to everyone else. The simplest version of this idea is a perfect circle of friends where every single person knows every other person directly. But real life is rarely perfect. In the messy reality of social circles or biological networks, a friend might not know your friend directly, yet they are still part of the same tight group because they share a mutual connection. This looser, more realistic definition of a close-knit group is what researchers call a "club." The challenge, which has puzzled mathematicians and computer scientists for years, is to find the smallest number of these clubs needed to cover an entire network, ensuring every single person or node belongs to at least one group.

For a long time, studying how to solve this puzzle was like trying to compare the speed of different cars without a standardized track. Researchers would test their methods on small, private sets of data, often hiding the exact rules they used or the specific starting conditions of their experiments. This made it nearly impossible to tell if one method was truly better than another or if it just got lucky with a specific setup. A new study from Tay Bac University in Vietnam aims to fix this confusion by building a massive, open, and perfectly transparent testing ground. The researchers have created a comprehensive library of thirty different networks, ranging from real-world examples like the neural pathways of a tiny worm and the social circles of a college football team, to highly complex, computer-generated maps designed to be difficult. They did not just run their tests once; they ran them 4,800 times, carefully controlling every variable to ensure that the results were not a fluke.

The core of this work is a rigorous experiment designed to see which computer programs are best at breaking these networks down into the fewest possible groups. The team tested eight different approaches, including simple, fast rules that make quick decisions, and more complex programs that learn and adapt as they go. To ensure a fair fight, every single program was given the exact same starting conditions, running through twenty different random scenarios to see how they performed under pressure. The results were clear: the programs that could learn and adjust their strategy during the process consistently found better solutions than those that followed a fixed set of rules. On the real-world networks, the adaptive programs were able to group the nodes into significantly tighter clusters, often reducing the number of groups needed by a noticeable margin compared to the older, static methods.

Perhaps most importantly, the researchers did not just trust the computer's word. Because the rules for these groups are strict—every member must be within a certain distance of every other member within the group—a single mistake in the calculation can invalidate the entire result. The team built a strict verification system that checked every single solution they found, confirming that every group they identified truly met the distance requirements. They found that one hundred percent of the solutions in their massive dataset were valid, a level of certainty that has been missing from previous studies. They also discovered that while some networks were easy to solve, others were surprisingly sensitive to how the computer started its work. On some complex networks, changing the starting point by just a tiny amount could lead to a much worse solution, highlighting why running many tests is essential.

This study does more than just find better ways to group data; it provides a new standard for how such problems should be studied in the future. By releasing all their data, the specific computer code they used, and the detailed logs of every single run, the author has handed the scientific community a tool to verify their own work. They have shown that when you remove the guesswork and the hidden variables, the most advanced, learning-based methods are indeed superior to the old, rigid approaches. The work serves as a foundation, a solid, verified benchmark that allows future researchers to build upon a known truth rather than chasing shadows. It turns a field that was once full of isolated, unrepeatable claims into one where progress can be measured, compared, and trusted, paving the way for more reliable discoveries in how we understand the complex webs that hold our world together.

Technical Summary: A Reproducible Benchmark Dataset and Experimental Evaluation for the Minimum s-Club Cover Problem

Problem Definition

The paper addresses the Minimum s-Club Cover (MSCC) problem, a combinatorial optimization challenge on graphs. Given a graph $G=(V, E)$ and an integer threshold $s \ge 1$ , an s-club is a subset of vertices $C \subseteq V$ such that the induced subgraph $G[C]$ is connected and has a diameter of at most $s$ (i.e., the shortest path between any two vertices in $C$ within $G[C]$ is $\le s$ ). The MSCC problem seeks a collection of s-clubs with the minimum cardinality whose union covers all vertices in $V$ .

The study focuses specifically on the case $s=2$ (the 2-club cover problem). This variant is significant because it models "triadic closure" in social networks (where non-adjacent members share a mutual neighbor) and local routing in telecommunication backbones. The problem is established as NP-hard and APX-hard, even on graphs with constant diameter or bipartite structures, with no polynomial-time approximation algorithm achieving a ratio better than $n^{1-\epsilon}$ unless $P=NP$ . A critical methodological challenge noted is that the s-club property is non-hereditary; removing a vertex from an s-club can invalidate the diameter constraint for the remaining subset, making feasibility verification non-trivial.

Methodology

To address the lack of standardized benchmarks and reproducibility in existing literature, the author constructed a comprehensive experimental framework involving the following components:

1. Benchmark Dataset Construction

The study curates a suite of 30 standardized graph instances divided into two categories:

Real-World Complex Networks (12 instances): Including biological networks (e.g., celegansneural, celegans_metabolic), social networks (e.g., karate, dolphins, polbooks), and collaboration/communication networks (e.g., email, netscience, jazz).
DIMACS Symmetric Benchmark Graphs (18 instances): Sourced from the Second DIMACS Implementation Challenge, including dense random graphs (e.g., C125.9, gen200), fault-tolerant graphs (c-fat), coding theory graphs (hamming, johnson), and Keller graphs.

For each instance, 10 topological metrics were computed, including vertex/edge counts, density, diameter, and clustering coefficients.

2. Experimental Protocol

The evaluation adheres to strict reproducibility standards:

Synchronized Random Seeds: All stochastic algorithms were executed using an identical vector of 20 pre-registered random seeds for every graph instance. This paired design eliminates variance caused by random initialization, enabling valid statistical comparison.
Algorithmic Baselines: Eight distinct algorithms were evaluated across three paradigms:
- Constructive Heuristics: I-MSM (Iterated Multi-Start Maximal 2-Club) and CCA (Clustering Coefficient-Aware).
- Static/Random Evolutionary Algorithms: Fixed-GGA, Random-GGA, and a No-RL baseline.
- Adaptive Learning-Augmented Baselines: Greedy-AOS, MAB-AOS (Multi-Armed Bandit), and PPO-AOS (Proximal Policy Optimization).
Strict Feasibility Verification: Every solution generated was independently verified using Breadth-First Search (BFS) and All-Pairs Shortest Path (APSP) calculations on the induced subgraphs. A solution is only valid if $\text{diam}(G[C]) \le 2$ for all clusters.

3. Data Architecture

The resulting dataset comprises 4,800 complete optimization runs (30 graphs $\times$ 8 algorithms $\times$ 20 seeds). The data is organized into:

Raw Logs: Per-run records including initial/final cover sizes, execution time, and feasibility flags.
Aggregated Metrics: Summary statistics (mean, std, median, worst-case) over the 20 seeds.
Statistical Analysis: Non-parametric Wilcoxon signed-rank tests with Holm-Bonferroni correction to control family-wise error rates.

Key Results

The experimental evaluation yielded several empirical findings:

Feasibility: The benchmark achieved a 100% feasibility rate across all 4,800 runs, confirming that the strict verification protocol successfully filtered invalid solutions.
Algorithmic Performance:
- Adaptive vs. Static: Adaptive operator selection methods (MAB-AOS, PPO-AOS) consistently outperformed static and random evolutionary baselines, achieving lower mean cover sizes and higher hit rates for optimal solutions.
- Constructive Heuristics: On highly dense DIMACS graphs (density $\rho \ge 0.7$ ), constructive heuristics (I-MSM, CCA) often found optimal covers ( $|C|_{min}=1$ or $2$) in sub-second times, outperforming evolutionary methods which required multiple generations to eliminate redundancy.
- Sparse Networks: On sparse, real-world networks (e.g., netscience, email), constructive heuristics suffered from local traps, resulting in covers up to 40% larger than those found by adaptive evolutionary search.
Seed Sensitivity:
- On structured DIMACS graphs, the "hit rate" (proportion of seeds finding the best solution) was often 100%, indicating deterministic convergence.
- On heterogeneous real-world networks, hit rates varied significantly (e.g., 5% to 80%), demonstrating that single-seed evaluations are insufficient for reliable benchmarking.
Statistical Significance: Non-parametric Wilcoxon tests confirmed that adaptive baselines (specifically PPO-AOS) showed statistically significant superiority over static operators and unguided baselines, with large effect sizes (Cliff's $\delta$ up to 0.88) and high statistical power ( $1-\beta > 0.95$ ).

Significance and Contributions

The paper positions itself not as a proposal of a new proprietary algorithm, but as a rigorous, community-accessible reference testbed designed to resolve methodological deficits in the field. Its primary contributions are:

Standardization: It provides the first standardized, open benchmark suite for the MSCC ( $s=2$ ) problem, addressing the absence of public, FAIR-compliant datasets in prior literature.
Reproducibility: By releasing raw per-seed logs, configuration files, and verification scripts, the author enables exact replication of results, countering the "reproducibility crisis" in ML4CO (Machine Learning for Combinatorial Optimization).
Methodological Rigor: The study enforces strict feasibility checking (often omitted in heuristic studies) and utilizes synchronized paired seeds to isolate algorithmic performance from random initialization noise.
Open Science: All artifacts (graph instances, raw data, aggregated metrics, and analysis scripts) are released under a Creative Commons Attribution 4.0 International (CC-BY 4.0) license, ensuring long-term accessibility and reusability.

The author concludes that this benchmark suite establishes an authoritative foundation for future comparative research in graph combinatorial optimization, operations research, and learning-augmented algorithm design, while acknowledging limitations such as the exclusive focus on $s=2$ and the lack of certified global optima for very large dense graphs due to MILP computational limits.