TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 19.01.2017


Page Content

to Navigation

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

Maximilian Katzmann (FSU Jena)


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=21.


Maximilian Katzmann
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe