Recurrence-based Heuristics for the Hamiltonian Path Inclusion and Exclusion and Exclusion Algorithm

Abstract

For many problem instances, the inclusion and exclusion formula has many cancellations and symmetries. By imposing a hierarchy on the formula's terms, we develop general reductions for inclusion and exclusion algorithms. We apply these reductions to an algorithm which counts Hamiltonian paths, and we develop a branch and bound algorithm to detect Hamiltonian paths. Then we show how to apply the reductions to other inclusion and exclusion algorithms.