TY - GEN
T1 - From backdoor key to backdoor completability
T2 - 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018
AU - Escamocher, Guillaume
AU - Siala, Mohamed
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - 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) [17] 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.
AB - 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) [17] 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.
UR - https://www.scopus.com/pages/publications/85048635378
U2 - 10.1007/978-3-319-93031-2_14
DO - 10.1007/978-3-319-93031-2_14
M3 - Conference proceeding
AN - SCOPUS:85048635378
SN - 9783319930305
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 198
EP - 214
BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, Proceedings
A2 - van Hoeve, Willem -Jan
PB - Springer Verlag
Y2 - 26 June 2018 through 29 June 2018
ER -