Technical Report No. 218 - Abstract

Joerg Hoffmann, Sebastian Kupferschmid
A Covering Problem for Hypercubes

We introduce a new NP-complete problem asking if a ``query'' hypercube is (not) covered by a set of other ``evidence'' hypercubes. This comes down to a form of constraint reasoning asking for the satisfiability of a CNF formula where the logical atoms are inequalities over single variables, with possibly infinite variable domains. We empirically investigate the location of the phase transition regions in two random distributions of problem instances. We introduce a solution method that iteratively constructs a representation of the non-covered part of the query cube. In particular, the method is not based on backtracking. Our experiments show that the method is, in a significant range of instances, superior to the backtracking method that results from translation to SAT, and application of a state-of-the-art DP-based SAT solver.