  Akiba and Iwata [TCS, 2016] demonstrated that a branch and reduce (B&R)
solver for the vertex cover problem can compete favorably with integer linear
programming solvers (e.g., CPLEX). Our research question is are there graph
characteristics that determine which reductions will be most effective? Not
only is the answer affirmative, but relevant characteristics are easy to
identify. To explore our ideas, we provide an enhanced version of the
Akiba-Iwata solver that can (a) be configured with any subset of reductions and
lower bounds; (b) print statistics such as time taken and number of vertices
reduced by each reduction. Based on extensive experiments with benchmark and
random instances we demonstrate that (i) more reductions do not necessarily
lead to better runtimes; (ii) the subset of reductions leading to the best (or
nearly the best) runtime can be predicted based on measurable characteristics
of a graph, e.g., density and degree distribution; and (iii) exceptions have
structural characteristics known in advance. Our primary contributions are 1. A
thorough examination reduction routine performance in the context of graph
characteristics. 2. Three primary hypotheses suggesting simple suites of
reductions as the most efficient options. 3. Experiments with a large corpus of
data to validate our hypotheses. 4. Measures that quantify a problem instance
on two key dimensions to make our hypotheses concrete. 5. An enhanced
open-source version of the Akiba-Iwata solver that enables our investigations
and creates opportunities for future exploration. Our main objective is to
provide guidance to a user so that, faced with a given problem instance or set
of instances, they may most effectively use the available reductions.
Ultimately these efforts can lead to an automated process.
