A Covering Problem for Hypercubes

Abstract

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 stateof-the-art DP-based SAT solver. This paper is an extended abstract. More details can be found in the long version of the paper [Hoffmann and Kupferschmid, 2005].