Bessiere, Christian ;
Carbonnel, Clément ;
Cooper, Martin C. ;
Hebrard, Emmanuel
Complexity of MinimumSize ArcInconsistency Explanations
Abstract
Explaining the outcome of programs has become one of the main concerns in AI research. In constraint programming, a user may want the system to explain why a given variable assignment is not feasible or how it came to the conclusion that the problem does not have any solution. One solution to the latter is to return to the user a sequence of simple reasoning steps that lead to inconsistency. Arc consistency is a wellknown form of reasoning that can be understood by a human. We consider explanations as sequences of propagation steps of a constraint on a variable (i.e. the ubiquitous revise function in arc consistency algorithms) that lead to inconsistency. We characterize, on binary CSPs, cases for which providing a shortest such explanation is easy: when domains are Boolean or when variables have maximum degree two. However, these polynomial cases are tight. Providing a shortest explanation is NPhard if the maximum degree is three, even if the number of variables is bounded, or if domain size is bounded by three. It remains NPhard on trees, despite the fact that arc consistency is a decision procedure on trees. Finally, the problem is not FPTapproximable unless the GapETH is false.
BibTeX  Entry
@InProceedings{bessiere_et_al:LIPIcs.CP.2022.9,
author = {Bessiere, Christian and Carbonnel, Cl\'{e}ment and Cooper, Martin C. and Hebrard, Emmanuel},
title = {{Complexity of MinimumSize ArcInconsistency Explanations}},
booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772402},
ISSN = {18688969},
year = {2022},
volume = {235},
editor = {Solnon, Christine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16638},
URN = {urn:nbn:de:0030drops166380},
doi = {10.4230/LIPIcs.CP.2022.9},
annote = {Keywords: Constraint programming, constraint propagation, minimum explanations, complexity}
}
23.07.2022
Keywords: 

Constraint programming, constraint propagation, minimum explanations, complexity 
Seminar: 

28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Issue date: 

2022 
Date of publication: 

23.07.2022 