Proceedings

Detecting and Exploiting Subproblem Tractability

Download BibTeX Cite

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

© 2013 International Joint Conferences on Artificial Intelligence

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.

  1. [Balasubramanian et al., 1998] R. Balasubramanian, Michael R. Fellows, and Venkatesh Raman. An Im- proved Fixed-Parameter Algorithm for Vertex Cover. Inf. Process. Lett., 65(3):163-168, 1998.
  2. [Bessiere and Debruyne, 2008] Christian Bessiere and Ro- muald Debruyne. Theoretical analysis of singleton arc consistency and its extensions. Artif. Intell., 172(1):29- 41, 2008.
  3. [Bessiere et al., 2011] Christian Bessiere, Stephane Cardon, Romuald Debruyne, and Christophe Lecoutre. Efficient Algorithms for Singleton Arc Consistency. Constraints, 16:25-53, 2011.
  4. [Bulatov and Dalmau, 2006] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for mal'tsev constraints. SIAM J. Comput., 36(1):16-27, 2006.
  5. [Bulatov, 2002] Andrei A. Bulatov. Mal'tsev constraints are tractable. Electronic Colloquium on Computational Com- plexity (ECCC), (034), 2002.
  6. [Chen et al., 2013] Hubie Chen, Victor Dalmau, and Berit Grußien. Arc Consistency and Friends. J Logic Computa- tion, 23(1):87-108, 2013.
  7. [Dechter and Pearl, 1987] R. Dechter and J. Pearl. The cycle-cutset method for improving search performance in ai applications. In Proceedings 3rd IEEE Conference on AI Applications, pages 224-230, Orlando FL, 1987.
  8. [Downey et al., 1999] R. G. Downey, M. R. Fellows, and U. Stege. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DI- MACS and DIMATIA to the Future, volume 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 49-99. 1999.
  9. [Freuder, 1982] Eugene C. Freuder. A sufficient condition for backtrack-free search. J. ACM, 29(1):24-32, 1982.
  10. [Jeavons et al., 1997] Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997.
  11. [Petke and Jeavons, 2009] Justyna Petke and Peter Jeavons. Tractable benchmarks for constraint programming. Tech- nical Report RR-09-07, OUCL, 2009.
  12. [Roussel and Lecoutre, 2009] Olivier Roussel and Christophe Lecoutre. Xml representation of con- straint networks: Format xcsp 2.
  13. [Williams et al., 2003] Ryan Williams, Carla P. Gomes, and Bart Selman. Backdoors to typical case complexity. In Proceedings of the 18th international joint conference on Artificial intelligence, IJCAI'03, pages 1173-1178, San Francisco, CA, USA, 2003. IJCAI

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards