Detecting and Exploiting Subproblem Tractability

Bessiere, Christian; Carbonnel, Clément; Hebrard, Emmanuel; Katsirelos, George; Walsh, Toby

Detecting and Exploiting Subproblem Tractability

Christian Bessière, Clément Carbonnel, Emmanuel Hebrard, George Katsirelos, Toby Walsh

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 468-473.

Abstract

Constraint satisfaction problems may be nearly tractable. For instance, most of the relations in a problem might belong to a tractable language. We introduce a method to take advantage of this fact by computing a backdoor to this tractable language. The method can be applied to many tractable classes for which the membership test is itself tractable. We introduce therefore two polynomial membership testing algorithms, to check if a language is closed under a majority or conservative Mal'tsev polymorphism, respectively. Then we show that computing a minimal backdoor for such classes is fixed parameter tractable (FPT) if the tractable subset of relations is given, and W[2]-complete otherwise. Finally, we report experimental results on the XCSP benchmark set. We identified a few promising problem classes where problems were nearly closed under a majority polymorphism and small backdoors could be computed.

Christian Bessiere, Clément Carbonnel, Emmanuel Hebrard, George Katsirelos, and Toby Walsh. 2013. Detecting and Exploiting Subproblem Tractability. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 468–473. https://ijcai.org/proceedings/2013/77

@inproceedings{ijcai2013p77,
  title     = {Detecting and Exploiting Subproblem Tractability},
  author    = {Bessiere, Christian and Carbonnel, Clément and Hebrard, Emmanuel and Katsirelos, George and Walsh, Toby},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {468--473},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/77},
}

TY  - CPAPER
TI  - Detecting and Exploiting Subproblem Tractability
AU  - Bessiere, Christian
AU  - Carbonnel, Clément
AU  - Hebrard, Emmanuel
AU  - Katsirelos, George
AU  - Walsh, Toby
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 468
EP  - 473
UR  - https://ijcai.org/proceedings/2013/77
ER  -