View article

The generalization of one problem to another is a useful technique in theoretical computer science; reductions among problems are a well established mathematical approach to demonstrate the structural relationships between problems. However, most of the reductions used to obtain theoretical results are relatively coarse-grained and chosen for their amenability in supporting mathematical proof, and represent a selection amongst many possible reduction schemas. We propose reexamining reductions as a practical tool, since choosing one reduction scheme over another may be decisive in solving a given instance in practical settings. In this work, we examine the impact of several new reduction schema. A total of 100 experiments were conducted using challenging Hamiltonian Cycle Problem instances using Concorde, a well known and effective TSP solver, and example of a complete memetic algorithm (MA …