The backdoor key: a path to understanding problem hardness

Abstract

We introduce our work on the backdoor key, a concept that shows promise for characterizing problem hardness in back-tracking search algorithms. The general notion of backdoors was recently introduced to explain the source of heavy-tailed behaviors in backtracking algorithms (Williams, Gomes, & Selman 2003a; 2003b). We describe empirical studies that show that the key faction,i.e., the ratio of the key size to the corresponding backdoor size, is a good predictor of problem hardness of ensembles and individual instances within an en-semble for structure domains with large key fraction.