You are here

From Backdoor Key to Backdoor Completability: Improving a Known Measure of Hardness for the Satisfiable CSP

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
Many studies have been conducted on the complexity of Constraint Satisfaction Problem (CSP) classes. However, there exists little theoretical work on the hardness of individual CSP instances. In this context, the backdoor key fraction (BKF) was introduced as a quantifier of problem hardness for individual satisfiable instances with regard to backtracking search. In our paper, after highlighting the weaknesses of the BKF, we propose a better characterization of the hardness of an individual satisfiable CSP instance based on the ratio between the size of the solution space and that of the search space. We formally show that our measure is negatively correlated with instance hardness. We also show through experiments that this measure evaluates more accurately the hardness of individual instances than the BKF.
Conference Name: 
15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Proceedings: 
15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Digital Object Identifer (DOI): 
Accepted
Publication Date: 
25/06/2018
Conference Location: 
Netherlands
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: