. References and . Balasubramanian, An Improved Fixed-Parameter Algorithm for Vertex Cover, Inf. Process. Lett, vol.65, issue.3, pp.163-168, 1998.

D. Bessiere, Theoretical analysis of singleton arc consistency and its extensions, Artificial Intelligence, vol.172, issue.1, pp.29-41, 2008.
DOI : 10.1016/j.artint.2007.09.001

URL : https://hal.archives-ouvertes.fr/lirmm-00230949

. Bessiere, Efficient algorithms for singleton arc consistency, Constraints, vol.177, issue.1, pp.25-53, 2011.
DOI : 10.1007/s10601-009-9080-5

URL : https://hal.archives-ouvertes.fr/hal-00487760

. Bulatov, . Dalmau, A. Andrei, V. Bulatov, and . Dalmau, A Simple Algorithm for Mal'tsev Constraints, SIAM Journal on Computing, vol.36, issue.1, pp.16-27, 2006.
DOI : 10.1137/050628957

A. Andrei and . Bulatov, Mal'tsev constraints are tractable, Electronic Colloquium on Computational Complexity (ECCC), issue.034, 2002.

P. Dechter, J. Dechter, and . Pearl, The cycle-cutset method for improving search performance in ai applications, Proceedings 3rd IEEE Conference on AI Applications, pp.224-230, 1987.

. Downey, Parameterized complexity: A framework for systematically confronting computational intractability, Contemporary Trends in Discrete Mathematics: From DI- MACS and DIMATIA to the Future DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp.49-99, 1999.
DOI : 10.1007/978-1-4612-0515-9

C. Eugene and . Freuder, A sufficient condition for backtrack-free search, J. ACM, vol.29, issue.1, pp.24-32, 1982.

. Jeavons, Closure properties of constraints, Journal of the ACM, vol.44, issue.4, pp.527-548, 1997.
DOI : 10.1145/263867.263489

J. Petke, C. Roussel, and . Lecoutre, Justyna Petke and Peter Jeavons Tractable benchmarks for constraint programming Xml representation of constraint networks: Format xcsp 2.1, 2009.

. Williams, Backdoors to typical case complexity, Proceedings of the 18th international joint conference on Artificial intelligence, IJCAI'03, pp.1173-1178, 2003.