Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs

Shaowei CaiIJCAI 2015

Introduction

The Minimum Vertex Cover (MinVC) problem is a cornerstone of combinatorial optimization and graph theory. It seeks the smallest set of vertices such that every edge in the graph is incident to at least one vertex in the set. While its applications range from network security to social network analysis, solving MinVC on modern "massive" graphs—those containing millions of vertices and edges—presents a significant scalability challenge. Traditional local search algorithms, while effective on smaller academic benchmarks, often become computationally prohibitive as the cost of selecting the "best" move scales with the size of the graph.

The FastVC Algorithm

To address this bottleneck, the authors propose FastVC, a local search algorithm designed for efficiency in the massive graph regime. FastVC shifts the focus from finding the absolute optimal move to finding a "sufficiently good" move quickly, utilizing two primary innovations:

1. Efficient Initialization (ConstructVC)

Standard algorithms often rely on greedy initialization strategies that can take $O(n^2)$ time. FastVC employs a two-phase ConstructVC approach:

  • Extending Phase: Iteratively scans edges and adds the endpoint with the higher degree to the cover if the edge is currently uncovered.
  • Shrinking Phase: Removes redundant vertices to ensure the resulting cover is minimal. This process operates in $O(m)$ time, where $m$ is the number of edges, providing a high-quality starting point for local search without the heavy pre-processing cost.

2. Best from Multiple Selections (BMS)

The core of FastVC's local search is the BMS heuristic. In traditional local search (like NuMVC), the algorithm scans all candidate vertices to find the one whose removal results in the minimum loss (uncovering the fewest edges), an $O(|V|)$ operation. BMS instead samples $k$ vertices at random (typically $k=50$) and selects the best among them. This reduces the per-step complexity to $O(1)$. Theoretically, a sample size of 50 provides a 99% probability of selecting a vertex within the top 10% of candidates, balancing heuristic guidance with extreme speed.

Experimental Evaluation

FastVC was benchmarked against the previous state-of-the-art, NuMVC, using 86 massive real-world graphs from the Network Data Repository. These datasets span social networks (Facebook, Twitter), web link graphs (Wikipedia, Google), and infrastructure networks, with some instances exceeding 3 million vertices and 50 million edges.

Comparison of runtime (seconds) between NumMVC and FastVC across various real-world graphs.

Key Results

  • Superior Speed: As shown in the runtime comparison, FastVC is often orders of magnitude faster than NuMVC. For instance, on the ia-wiki-Talk graph, FastVC reached a solution in 8.6 seconds, while NuMVC required over 510 seconds.
  • Improved Solution Quality: FastVC found smaller vertex covers in 46 of the 86 cases and matched NuMVC in 37 others.
  • Robustness on Massive Scales: On the largest graphs where NuMVC often failed to find any valid cover within a 1000-second limit (indicated as 'n/a' in the data), FastVC consistently provided high-quality solutions.
Performance comparison on massive social and web graphs, highlighting FastVC's ability to handle instances where NuMVC fails (n/a).

Discussion and Insights

The success of FastVC highlights the "Good Enough" principle in massive data regimes: a "perfect" move that takes a second is often less valuable than a "good" move that takes a millisecond. By the time a complex heuristic makes one decision, a lightweight heuristic can explore thousands of potential states. The BMS strategy effectively uses randomness as a complexity filter, demonstrating that global optimization can be approximated through local sampling.

Conclusion

FastVC represents a paradigm shift in local search for graph problems. By prioritizing low-complexity heuristics like BMS and $O(m)$ construction, it achieves a superior balance between solution quality and computational time. Future work may extend these principles to weighted graphs or other NP-hard problems such as Maximum Clique and Graph Coloring.

Summary updated

BibTeX
@inproceedings{cai2015balance,
  author = {Shaowei Cai},
  title = {{Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure