  Several NP-hard problems are solved exactly using exponential-time branching
strategies, whether it be branch-and-bound algorithms, or bounded search trees
in fixed-parameter algorithms. The number of tractable instances that can be
handled by sequential algorithms is usually small, whereas massive
parallelization has been shown to significantly increase the space of instances
that can be solved exactly. However, previous centralized approaches require
too much communication to be efficient, whereas decentralized approaches are
more efficient but have difficulty keeping track of the global state of the
exploration.
  In this work, we propose to revisit the centralized paradigm while avoiding
previous bottlenecks. In our strategy, the center has lightweight
responsibilities, requires only a few bits for every communication, but is
still able to keep track of the progress of every worker. In particular, the
center never holds any task but is able to guarantee that a process with no
work always receives the highest priority task globally.
  Our strategy was implemented in a generic C++ library called GemPBA, which
allows a programmer to convert a sequential branching algorithm into a parallel
version by changing only a few lines of code. An experimental case study on the
vertex cover problem demonstrates that some of the toughest instances from the
DIMACS challenge graphs that would take months to solve sequentially can be
handled within two hours with our approach.
