Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization

Wanru Gao, Tobias Friedrich, Timo Kötzing, Frank Neumann

Abstract

We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.
BibTeX
@inproceedings{gao2017scaling,
  author = {Wanru Gao and Tobias Friedrich and Timo Kötzing and Frank Neumann},
  title = {{Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization}},
  booktitle = {Australasian Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1007/978-3-319-63004-5\_11},
}

Loading related content...

Figure