TL;DR
This paper introduces InfVC, a novel local search algorithm for the Minimum Vertex Cover (MVC) problem on massive graphs. InfVC combines an inference-driven optimization strategy, a structure-aware perturbation mechanism, and a self-adaptive search framework to achieve state-of-the-art performance, outperforming existing algorithms on nearly all tested instances.
What Problem Does This Paper Address?
The Minimum Vertex Cover (MVC) problem is a classic NP-hard problem with significant real-world applications. While exact algorithms guarantee optimality, they are computationally infeasible for large graphs. Approximation algorithms offer guarantees but often yield suboptimal solutions. Heuristic algorithms, particularly local search methods, are widely used to find high-quality solutions efficiently. However, existing heuristic approaches for MVC on massive graphs often overlook the potential of inference rules to directly improve solution quality and fail to fully leverage the structural characteristics of high-quality solutions. This paper aims to bridge this gap by proposing an inference-enhanced local search algorithm that addresses these limitations.
Methods
InfVC is built upon three core ideas:
- Inference-Driven Optimization Strategy: This strategy directly improves the quality of a feasible solution by identifying "critical addition vertices." These are vertices that, when added to the current cover, allow for the removal of two other vertices from the cover while still maintaining a valid vertex cover. This process can reduce the size of the vertex cover.
- Structural-Determined Perturbation Strategy: This approach leverages an observation that high-quality vertex covers tend to include vertices with higher degrees. The perturbation strategy prioritizes adding high-degree vertices and removing low-degree vertices, aiming to guide the search towards more promising regions of the solution space and escape local optima.
- Self-Adaptive Local Search Framework: This framework organizes the search into three phases: stochastic search (for exploration), perturbation (to escape local optima), and convergence search (for rapid refinement). A perturbation management mechanism dynamically switches between these phases based on the search progress, balancing exploration and exploitation.
The algorithm also incorporates preprocessing steps to simplify the graph and handles disconnected components efficiently.
Datasets
The paper evaluates InfVC on a collection of massive graphs. Specifically, it uses 102 instances from the Network Data Repository [Rossi and Ahmed, 2015] and an additional 72 instances from the same repository, totaling 156 unique instances after accounting for duplicates. These datasets are commonly used in MVC research.
Key Insights and Ideas
- Inference Rules for Direct Improvement: The paper demonstrates that inference rules, specifically identifying "critical addition vertices," can directly improve the quality of a vertex cover solution without relying on traditional local search moves. This is a novel approach to enhancing solution quality.
- Structure Matters: The observation that high-degree vertices are more prevalent in high-quality vertex covers is a crucial insight. This structural characteristic is leveraged to design a more effective perturbation strategy that guides the search more intelligently than random or score-based methods.
- Adaptive Search is Key: The self-adaptive framework, which dynamically switches between exploration, perturbation, and exploitation phases, is essential for efficiently navigating the complex search space of massive graphs. This adaptability allows the algorithm to respond to different stages of the search process.
- All Components Contribute: Experimental results show that disabling any of the three core strategies (inference, structural perturbation, or self-adaptive framework) leads to a significant performance degradation, highlighting the synergistic nature of the proposed components.
Key Results
- InfVC significantly outperforms state-of-the-art heuristic algorithms on almost all tested instances.
- On the 82 instances that were not trivially solvable after preprocessing, InfVC found the best minimal solutions on 71 instances and the best average solutions on 78 instances, outperforming other algorithms by a substantial margin.
- InfVC also surpasses best-record solutions on 31 instances.
- When compared to exact algorithms (CPLEX and B&R), InfVC outperforms them on 41 and 48 instances, respectively, within a 3600-second time limit, demonstrating its effectiveness for large-scale problems where exact methods fail.
- The inference-driven optimization strategy alone provides significant average improvement across many instances.
Limitations and Future Work
- Preprocessing Dependency: While InfVC's performance is strong, its effectiveness is partly reliant on the preprocessing step. The paper notes that applying the same advanced preprocessing to other algorithms improves their performance, but InfVC's advantage persists.
- Future Work: The authors plan to develop a "pseudo-reduction-based heuristic algorithm" that integrates reduction techniques directly into the heuristic search process, rather than as a separate preprocessing step.
Summary updated