A parallel search tree algorithm for vertex cover on graphical processing units. (c2013)

Abstract

Graphical Processing Units (GPUs) have become popular recently due their highly parallel shared-memory architectures. The computational challenge posed by NP-Hard problems makes them potential targets to GPU-based computations, especially when solved by exact exponential-time algorithms. Using the classical NP-hard Vertex Cover problem as a case study, we provide a framework for GPU-based solutions by exploiting the highly parallel structure of the GPU to accelerate the expansion of search-states in commonly used recursive backtracking algorithms. Experimental results show that our method can achieve huge speedups on randomly generated sparse graphs, as well as hard instances from the DIMACS benchmark.