Document Open Access Logo

Complexity of Minimum-Size Arc-Inconsistency Explanations

Authors Christian Bessiere , Clément Carbonnel , Martin C. Cooper , Emmanuel Hebrard

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.9.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Christian Bessiere
  • CNRS, University of Montpellier, France
Clément Carbonnel
  • CNRS, University of Montpellier, France
Martin C. Cooper
  • IRIT, University of Toulouse, France
Emmanuel Hebrard
  • LAAS CNRS, Toulouse, France

Funding

This work was supported by the AI Interdisciplinary Institute ANITI, funded by the French program "Investing for the Future – PIA3" under grant agreement no. ANR-19-PI3A-0004. The first two authors received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 952215.

Cite AsGet BibTex

Christian Bessiere, Clément Carbonnel, Martin C. Cooper, and Emmanuel Hebrard. Complexity of Minimum-Size Arc-Inconsistency Explanations. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CP.2022.9

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 well-known 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 NP-hard if the maximum degree is three, even if the number of variables is bounded, or if domain size is bounded by three. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. Finally, the problem is not FPT-approximable unless the Gap-ETH is false.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Constraint programming
  • constraint propagation
  • minimum explanations
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jérôme Amilhastre, Hélène Fargier, and Pierre Marquis. Consistency restoration and explanations in dynamic CSPs application to configuration. Artif. Intell., 135(1-2):199-234, 2002. URL: https://doi.org/10.1016/S0004-3702(01)00162-X.
  2. Bart Bogaerts, Emilio Gamba, and Tias Guns. A framework for step-wise explaining how to solve constraint satisfaction problems. Artif. Intell., 300:103550, 2021. URL: https://doi.org/10.1016/j.artint.2021.103550.
  3. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In Chris Umans, editor, Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS'17), pages 743-754. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.74.
  4. Yijia Chen, Martin Grohe, and Magdalena Grüber. On parameterized approximability. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC, volume 4169 of Lecture Notes in Computer Science, pages 109-120. Springer, 2006. URL: https://doi.org/10.1007/11847250_10.
  5. Martin C. Cooper, Simon de Givry, Martí Sánchez-Fibla, Thomas Schiex, and Matthias Zytnicki. Virtual arc consistency for weighted CSP. In Dieter Fox and Carla P. Gomes, editors, AAAI 2008, pages 253-258. AAAI Press, 2008. URL: http://www.aaai.org/Library/AAAI/2008/aaai08-040.php.
  6. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity, page 128, 2016. Google Scholar
  7. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979. Google Scholar
  8. Allen Van Gelder. Verifying RUP proofs of propositional unsatisfiability. In ISAIM, 2008. Google Scholar
  9. E. Goldberg and Y. Novikov. Verification of proofs of unsatisfiability for CNF formulas. In 2003 Design, Automation and Test in Europe Conference and Exhibition, pages 886-891, 2003. URL: https://doi.org/10.1109/DATE.2003.1253718.
  10. Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction-based explanations for machine learning models. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1511-1519, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33011511.
  11. Ulrich Junker. QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In Deborah L. McGuinness and George Ferguson, editors, Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, pages 167-172. AAAI Press / The MIT Press, 2004. Google Scholar
  12. Ulrich Junker. Configuration. In Francesca Rossi, Peter van Beek, and Toby Walsh, editors, Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence, pages 837-873. Elsevier, 2006. Google Scholar
  13. R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  14. Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP'17), volume 80 of LIPIcs, pages 78:1-78:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.78.
  15. Dániel Marx. Completely inapproximable monotone and antimonotone parameterized problems. In Proceedings of the 25th IEEE Annual Conference on Computational Complexity, pages 181-187, 2010. URL: https://doi.org/10.1109/CCC.2010.25.
  16. Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach to explaining Bayesian network classifiers. In IJCAI'18, pages 5103-5111. AAAI Press, 2018. Google Scholar
  17. Mohammed H. Sqalli and Eugene C. Freuder. Inference-based constraint satisfaction supports explanation. In William J. Clancey and Daniel S. Weld, editors, AAAI 96, IAAI 96, Volume 1, pages 318-325. AAAI Press / The MIT Press, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact