Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem

Maximilian Katzmann, Christian Komusiewicz

Introduction

The Minimum Vertex Cover (MVC) problem—identifying the smallest set of vertices that covers every edge in a graph—is a fundamental NP-hard challenge with wide-ranging applications in network analysis. To handle large-scale graphs, researchers typically rely on local search heuristics. However, these methods often become trapped in local optima because they are restricted to small neighborhoods (e.g., $k \le 5$) to avoid the exponential time complexity of larger searches. This paper investigates the feasibility and benefits of systematically exploring much larger neighborhoods, up to $k=21$.

Methodology

The authors developed a systematic search tree algorithm that leverages the structural properties of real-world networks to make large-neighborhood searches computationally tractable. The approach is built on three key technical insights:

  1. Connected Swaps: The authors prove that if an improving vertex cover exists within distance $k$, there must exist a connected swap that improves the cover. This drastically narrows the search space compared to arbitrary swaps.
  2. Parameterized Complexity: The algorithm is designed to be Fixed-Parameter Tractable (FPT) with a running time of $O(2^k(\Delta - 1)^{k/2} \cdot k \cdot n)$, where $\Delta$ is the maximum degree of the graph. This makes the search efficient for sparse real-world networks.
  3. Advanced Pruning Rules: To further accelerate the search, the authors implemented pruning based on sub-tree analysis (discarding branches that cannot lead to net improvement) and lower-bound packing (estimating the minimum vertices needed to cover remaining edges).

Experimental Evaluation

The algorithm was tested on 35 real-world networks from the KONECT, DIMACS, and Network Data Repository collections. These datasets range from small social graphs to massive citation networks with over 500,000 nodes and 16 million edges.

Computational Feasibility

A central finding of the study is that searching large neighborhoods is practically feasible for real-world instances.

Computational time (seconds) across different neighborhood sizes k.

As shown in the timing data, while the search time increases with $k$, the pruning rules and FPT design keep the computation within reasonable limits, even for $k \approx 20$ on graphs with hundreds of thousands of vertices.

Solution Quality and Optimality

Increasing the neighborhood size directly translates to higher solution quality. The authors found that for 91% of the benchmark instances, a neighborhood radius of $k=21$ was sufficient to reach the globally optimal solution.

Relative improvement in vertex cover size as the neighborhood size k increases.

While significant improvements are often realized by $k=9$, the continued search up to $k=21$ is what ultimately secures optimality in harder instances. When used as a post-processor for state-of-the-art heuristics like FastVC, the $k$-swap algorithm found improvements of up to 25 vertices in just a few minutes on instances where the heuristic had plateaued.

Conclusion

This research demonstrates that the conventional restriction of local search to tiny neighborhoods is unnecessary for many real-world graphs. By utilizing systematic exploration and clever pruning, it is possible to search neighborhoods large enough to reach global optimality. This approach offers a powerful tool for enhancing existing MVC solvers and could potentially be generalized to other combinatorial problems like the Minimum Dominating Set.

Summary updated

Abstract

We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of k , it is feasible and worthwhile to determine, given a graph G with vertex cover C , if there is a k -swap S such that ( C ∖ S ) ∪ ( S ∖ C ) is a smaller vertex cover of G . First, we describe an algorithm running in ∆ O(k) ⋅ n time for searching the k -swap neighborhood on n -vertex graphs with maximum degree ∆. Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for k ≈ 20. Finally, we show that it is worthwhile to consider moderately-sized k -swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius k of the local search neighborhood and that in most cases optimal solutions can be found by setting k
BibTeX
@inproceedings{katzmann2017systematic,
  author = {Maximilian Katzmann and Christian Komusiewicz},
  title = {{Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10659},
}
Figure