Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess

Shaowei Cai, Jinkun Lin, Chuan Luo

TL;DR

This paper tackles the NP-hard Minimum Vertex Cover (MinVC) problem on massive, real-world graphs. The authors introduce novel construction and local search algorithms (FastVC) that are significantly faster and more effective than existing methods on these large-scale datasets. They also propose a preprocessing technique that further enhances performance, leading to improved MinVC solvers.

What Problem Does This Paper Address?

The Minimum Vertex Cover (MinVC) problem is a fundamental challenge in combinatorial optimization with applications ranging from network security to molecular biology. It involves finding the smallest set of vertices in a graph such that every edge has at least one endpoint in this set. While MinVC is NP-hard, meaning finding an exact optimal solution is computationally infeasible for large graphs, heuristic algorithms aim to find good approximate solutions efficiently.

However, existing heuristic algorithms often struggle with "massive sparse graphs" – real-world datasets with millions of vertices and edges that are still relatively sparse. These graphs pose challenges due to their sheer size, making high-complexity heuristics impractical. This paper addresses this gap by developing and evaluating techniques specifically designed for these massive sparse graphs, focusing on balancing computational complexity with solution quality.

Methods

The paper introduces several key algorithmic components:

  • EdgeGreedyVC (Construction Algorithm): This novel algorithm constructs an initial vertex cover. It features an "extending phase" that greedily adds vertices to cover edges, prioritizing vertices with higher degrees. This is followed by a "shrinking phase" that removes redundant vertices from the cover without compromising its validity. EdgeGreedyVC boasts a linear time complexity of O(m), where m is the number of edges.
  • FastVC (Local Search Algorithm): This algorithm builds upon EdgeGreedyVC for its initial solution. Its core innovation lies in the "Best from Multiple Selections" (BMS) heuristic for choosing which vertex to remove from the candidate cover during local search. BMS uses a probabilistic approach to select a vertex that is likely to have a low loss value (i.e., removing it won't uncover many edges), significantly reducing the complexity of this step from O(|V|) to O(1) compared to previous methods. This allows FastVC to perform more search steps within a given time limit.
  • Preprocessing Algorithm (D1+D2+Dom): This algorithm simplifies the graph before applying MinVC solvers. It uses a combination of three reduction rules: Degree-1, Degree-2, and Dominance rules. These rules iteratively remove vertices or fix them as part of the cover, reducing the graph's size. The algorithm operates in two phases, first using Degree-1 and Degree-2 rules, then applying the Dominance rule.
  • Improved Solvers (NuMVC2, FastVC2, NuMVC2+p, FastVC2+p): The authors integrate their construction algorithms and preprocessing techniques with existing state-of-the-art solvers (NuMVC) to create improved versions. NuMVC2 and FastVC2 combine three construction heuristics (including EdgeGreedyVC and improved versions of GreedyVC and MatchVC) to generate a better initial solution. NuMVC2+p and FastVC2+p further incorporate the preprocessing algorithm.

Datasets

The authors evaluated their algorithms on a broad range of real-world massive graphs collected from the Network Data Repository online. These graphs span various categories, including biological networks, collaboration networks, interaction networks, infrastructure networks, Amazon recommendation networks, Tweeter networks, Facebook networks, scientific computation networks, social networks, and technological networks. The paper notes that these graphs are often very large, with millions of vertices and tens of millions of edges, and are generally sparse. They also mention using the DIMACS and BHOSLIB benchmark sets for comparison with previous work, though their primary experiments focus on the larger, real-world datasets.

Key Insights and Ideas

  • Low-Complexity Heuristics are Crucial for Massive Graphs: The paper strongly emphasizes that for graphs with millions of vertices, the time complexity of heuristics is a critical bottleneck. Algorithms with high polynomial complexity, like the O(n²) greedy approach, become impractical.
  • Probabilistic Selection for Efficiency: The BMS heuristic in FastVC demonstrates that a probabilistic approach to selecting candidate vertices for removal can achieve near-optimal quality with significantly reduced computational cost, making it highly effective for massive datasets.
  • Preprocessing as a Powerful Simplifier: The D1+D2+Dom preprocessing algorithm significantly reduces graph size, making subsequent MinVC solvers much more efficient and sometimes enabling them to find better solutions.
  • Complementarity of Construction Heuristics: Integrating multiple construction heuristics (as done in NuMVC2 and FastVC2) can lead to better initial solutions for local search, improving overall performance.

Key Results

  • FastVC Outperforms NuMVC: FastVC significantly outperforms the state-of-the-art algorithm NuMVC on massive graphs, finding better vertex covers for 52 out of 102 graphs and achieving comparable or better quality on most others.
  • Speedup: FastVC is considerably faster than NuMVC, especially on graphs where they find similar quality solutions.
  • Preprocessing Effectiveness: The D1+D2+Dom preprocessing algorithm effectively reduces graph sizes, with some instances being completely solved by the preprocessing alone. The combined solvers (NuMVC2+p and FastVC2+p) show improved performance over their non-preprocessed counterparts.
  • EdgeGreedyVC Balance: EdgeGreedyVC strikes a good balance between solution quality and run time, making it a strong candidate for constructing initial vertex covers.

Limitations and Future Work

  • Limitations:
    • While the paper focuses on sparse graphs, it acknowledges the existence of dense graphs from real-world applications, for which their methods might be less effective.
  • The paper does not explicitly discuss the theoretical approximation guarantees of their heuristic algorithms, focusing more on practical performance.
  • Future Work:
    • The authors aim to design even more efficient heuristic algorithms for MinVC and other graph problems on massive graphs.
  • They are interested in applying the ideas developed in this work to solve large instances of other combinatorial problems.

Summary updated

Abstract

The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.
BibTeX
@article{cai2017finding,
  author = {Shaowei Cai and Jinkun Lin and Chuan Luo},
  title = {{Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  doi = {10.1613/jair.5443},
}
Figure