R. L. Abu-khzam, . Collins, R. Michael, . Fellows, A. Michael et al., Comparison of approaches on Balanced Vertex Cover: dimacs [1] Faisal N Kernelization algorithms for the vertex cover problem: Theory and experiments, p.69, 2004.

N. Faisal, . Abu-khzam, R. Michael, . Fellows, A. Michael et al., Crown structures for vertex cover kernelization, Theory of Computing Systems, pp.411-430, 2007.

R. Noga-alon, U. Yuster, and . Zwick, Color-coding, Journal of the ACM, vol.42, issue.4, pp.844-856, 1995.
DOI : 10.1145/210332.210337

L. Barto, The Dichotomy for Conservative Constraint Satisfaction Problems Revisited, 2011 IEEE 26th Annual Symposium on Logic in Computer Science, pp.301-310, 2011.
DOI : 10.1109/LICS.2011.25

L. Barto, Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms, Journal canadien de math??matiques, vol.65, issue.1, pp.3-21, 2013.
DOI : 10.4153/CJM-2011-087-3

L. Barto, The collapse of the bounded width hierarchy, Journal of Logic and Computation, vol.26, issue.3, pp.923-943, 2016.
DOI : 10.1093/logcom/exu070

L. Barto and M. Kozik, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Journal of the ACM, vol.61, issue.1, p.2014
DOI : 10.1145/2556646

L. Barto, M. Kozik, and T. Niven, The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell), SIAM Journal on Computing, vol.38, issue.5, pp.1782-1802, 2009.
DOI : 10.1137/070708093

L. Barto and D. Stanovsk´ystanovsk´y, Polymorphisms of small digraphs, Novi Sad Journal of Mathematics, vol.40, issue.2, pp.95-109, 2010.

J. Berman, P. Idziak, R. Markovi´cmarkovi´c, M. Mckenzie, R. Valeriote et al., Varieties with few subalgebras of powers. Transactions of the, pp.1445-1473, 2010.

C. Bessiere, C. Carbonnel, E. Hebrard, G. Katsirelos, and T. Walsh, Detecting and exploiting subproblem tractability, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp.468-474, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00830330

C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, C. Quimper et al., The Parameterized Complexity of Global Constraints, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, pp.235-240, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00272791

C. Bessiere, E. Hebrard, B. Hnich, and T. Walsh, The Tractability of Global Constraints, Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, pp.716-720, 2004.
DOI : 10.1007/978-3-540-30201-8_53
URL : https://hal.archives-ouvertes.fr/lirmm-00108916

C. Bessiere, E. Hebrard, G. Katsirelos, Z. Kiziltan, and T. Walsh, Ranking constraints, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp.705-711, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-01374715

L. Hans, B. M. Bodlaender, S. Jansen, and . Kratsch, Kernelization lower bounds by cross-composition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014.

L. Bordeaux, M. Cadoli, and T. Mancini, A unifying framework for structural properties of csps: Definitions, complexity, tractability, Journal of Artificial Intelligence Research, vol.32, pp.607-629, 2008.

A. A. Bulatov, Mal'tsev constraints are tractable, 2002.

A. A. Bulatov, Combinatorial problems raised from 2-semilattices, Journal of Algebra, vol.298, issue.2, pp.321-339, 2006.
DOI : 10.1016/j.jalgebra.2004.07.044
URL : http://doi.org/10.1016/j.jalgebra.2004.07.044

A. A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM, vol.53, issue.1, pp.66-120, 2006.
DOI : 10.1145/1120582.1120584

A. A. Bulatov, Bounded relational width, 2010.

A. A. Bulatov, Complexity of conservative constraint satisfaction problems, ACM Transactions on Computational Logic, vol.12, issue.4, p.24, 2011.
DOI : 10.1145/1970398.1970400

A. A. Bulatov, Conservative constraint satisfaction re-revisited, Journal of Computer and System Sciences, vol.82, issue.2, pp.347-356, 2016.
DOI : 10.1016/j.jcss.2015.07.004
URL : http://arxiv.org/abs/1408.3690

A. A. Bulatov, Graphs of relational structures, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, pp.642-651, 2016.
DOI : 10.1145/2933575.2933604

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.

A. Andrei, P. G. Bulatov, and . Jeavons, Algebraic structures in combinatorial problems, 2001.

A. A. Bulatov, P. G. Jeavons, and A. A. Krokhin, Classifying the Complexity of Constraints Using Finite Algebras, SIAM Journal on Computing, vol.34, issue.3, pp.720-742, 2005.
DOI : 10.1137/S0097539700376676

A. Andrei, D. Bulatov, and . Marx, The complexity of global cardinality constraints, Logical Methods in Computer Science, vol.6, pp.1-27, 2010.

J. F. Buss and J. Goldsmith, Nondeterminism within $P^ * $, SIAM Journal on Computing, vol.22, issue.3, pp.560-572, 1993.
DOI : 10.1137/0222038

Y. Cao and D. Marx, Interval deletion is fixed-parameter tractable, ACM Transactions on Algorithms, vol.11, issue.3, p.21, 2015.
DOI : 10.1137/1.9781611973402.9
URL : http://arxiv.org/abs/1211.5933

C. Carbonnel, The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable, Proceedings of the Twenty-Second International Conference on Principles and Practice of Constraint Programming, pp.130-146, 2016.
DOI : 10.1007/978-3-319-44953-1_9
URL : https://hal.archives-ouvertes.fr/hal-01413124

C. Carbonnel, The Meta-Problem for Conservative Mal'tsev Constraints, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01230681

C. Carbonnel and M. C. Cooper, Tractability in constraint satisfaction problems: a survey, Constraints, vol.13, issue.1???2, pp.115-144, 2016.
DOI : 10.1007/s10601-015-9198-6
URL : https://hal.archives-ouvertes.fr/hal-01230685

C. Carbonnel, M. C. Cooper, and E. Hebrard, On Backdoors to Tractable Constraint Languages, Proceedings of the Twentieth International Conference on Principles and Practice of Constraint Programming, pp.224-239, 2014.
DOI : 10.1007/978-3-319-10428-7_18
URL : https://hal.archives-ouvertes.fr/hal-01154625

C. Carbonnel and E. Hebrard, Propagation via Kernelization: The Vertex Cover Constraint, Proceedings of the Twenty-Second International Conference on Principles and Practice of Constraint Programming, pp.147-156, 2016.
DOI : 10.1007/978-3-319-44953-1_10
URL : https://hal.archives-ouvertes.fr/hal-01459870

C. Carvalho, L. Egri, M. Jackson, and T. Niven, On Maltsev Digraphs, In Computer Science?Theory and Applications, vol.59, issue.3-4, pp.181-194
DOI : 10.1007/s00012-008-2122-9

H. Chen and B. Larose, Asking the metaquestions in constraint tractability, ACM Transactions on Computation Theory, 2017.

J. Chen, X. Huang, I. A. Kanj, and G. Xia, Strong computational lower bounds via parameterized complexity, Journal of Computer and System Sciences, vol.72, issue.8, pp.1346-1367, 2006.
DOI : 10.1016/j.jcss.2006.04.007
URL : http://doi.org/10.1016/j.jcss.2006.04.007

J. Chen, I. A. Kanj, and G. Xia, Improved Parameterized Upper Bounds for Vertex Cover, Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp.238-249, 2006.
DOI : 10.1007/11821069_21
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.432.831

M. Chlebík and J. Chlebíková, Crown reductions for the Minimum Weighted Vertex Cover problem, Discrete Applied Mathematics, vol.156, issue.3, pp.292-312, 2008.
DOI : 10.1016/j.dam.2007.03.026

A. Cobham, The intrinsic computational difficulty of functions, Proceedings of the International Congress for Logic, Methodology, and Philosophy of Science, pp.24-30, 1964.

A. Stephen and . Cook, The complexity of theorem-proving procedures, Proceedings of the Third annual ACM symposium on Theory of Computing, pp.151-158, 1971.

C. Martin, D. A. Cooper, P. Cohen, and . Jeavons, Characterising tractable constraints, Artificial Intelligence, vol.65, issue.2, pp.347-361, 1994.

C. Martin and S. Cooper, Hybrid tractable classes of constraint problems, The Constraint Satisfaction Problem: Complexity and Approximability, 2017.

N. Creignou, A. Meier, J. Müller, J. Schmidt, and H. Vollmer, Paradigms for Parameterized Enumeration, Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp.290-301, 2013.
DOI : 10.1016/j.tcs.2012.12.039
URL : https://hal.archives-ouvertes.fr/hal-01194386

V. Dalmau, Generalized Majority-Minority Operations are Tractable, Logical Methods in Computer Science, vol.2, issue.4, 2006.
DOI : 10.2168/LMCS-2(4:1)2006
URL : http://arxiv.org/abs/cs/0609108

V. Dalmau, There are no pure relational width 2 constraint satisfaction problems, Information Processing Letters, vol.109, issue.4, pp.213-218, 2009.
DOI : 10.1016/j.ipl.2008.10.005
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.596.4467

V. Dalmau and B. Larose, Mal'tsev + datalog ? symmetric datalog, Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, pp.297-306, 2008.
DOI : 10.1109/lics.2008.14

V. Dalmau and J. Pearson, Set functions and width 1 problems, Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming, pp.159-173, 1999.
DOI : 10.1007/978-3-540-48085-3_12
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.3161

P. Damaschke, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theoretical Computer Science, vol.351, issue.3, pp.337-350, 2006.
DOI : 10.1016/j.tcs.2005.10.004
URL : http://dx.doi.org/10.1016/j.tcs.2005.10.004

P. David, Using pivot consistency to decompose and solve functional CSPs, Journal of Artificial Intelligence Research, vol.2, pp.447-474, 1995.
URL : https://hal.archives-ouvertes.fr/hal-00442813

R. Dechter, Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition, Artificial Intelligence, vol.41, issue.3, pp.273-312, 1990.
DOI : 10.1016/0004-3702(90)90046-3

R. Dechter, Constraint Processing, 2003.

K. H. Frank, M. R. Dehne, M. A. Fellows, F. A. Langston, K. Rosamond et al., An O(2 o(k) n 3 ) FPT algorithm for the undirected feedback vertex set problem, Proceedings of the Eleventh Annual Conference on Computing and Combinatorics, pp.859-869, 2005.

Y. Deville, O. Barette, and P. Van-hentenryck, Constraint satisfaction over connected row-convex constraints, Artificial Intelligence, vol.109, issue.1-2, pp.243-271, 1999.
DOI : 10.1016/S0004-3702(99)00012-0
URL : http://doi.org/10.1016/s0004-3702(99)00012-0

B. Dilkina, C. P. Gomes, A. Sabharwal-rod, G. Downey, R. Michael et al., Tradeoffs in the complexity of backdoor detection Fixed-parameter tractability and completeness I: Basic results, Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming, pp.256-270873, 1995.

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, vol.141, issue.1-2, pp.109-131, 1995.
DOI : 10.1016/0304-3975(94)00097-3

G. Rodney, M. R. Downey, and . Fellows, Parameterized complexity, 2012.

M. Dyer and D. Richerby, An Effective Dichotomy for the Counting Constraint Satisfaction Problem, SIAM Journal on Computing, vol.42, issue.3, pp.1245-1274, 2013.
DOI : 10.1137/100811258

G. Escamocher, O. Barry, and . Sullivan, On the Minimal Constraint Satisfaction Problem: Complexity and Generation, Proceedings of the Ninth International Conference on Combinatorial Optimization and Applications, pp.731-745, 2015.
DOI : 10.1007/978-3-319-26626-8_54

T. Feder and M. Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, vol.28, issue.1, pp.57-104, 1998.
DOI : 10.1137/S0097539794266766

K. Johannes, S. Fichte, and . Szeider, Backdoors to normality for disjunctive logic programs, ACM Transactions on Computational Logic, vol.17, issue.1, p.7, 2015.

J. K. , F. , and S. Szeider, Backdoors to tractable answer set programming, Artificial Intelligence, vol.220, pp.64-103, 2015.

E. C. Freuder, Complexity of k-tree structured constraint satisfaction problems, Proceedings of the 8th National Conference on Artificial Intelligence, pp.4-9, 1990.

R. Ganian, M. S. Ramanujan, and S. Szeider, Backdoors to Tractable Valued CSP, Proceedings of the 22nd International Conference on Principles and Practice of Constraint Programming, 2016.
DOI : 10.1007/978-3-319-44953-1_16
URL : http://arxiv.org/abs/1612.05733

M. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.

S. Garg and G. Philip, : Fixed-parameter Tractability Above A Higher Guarantee, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1152-1166, 2016.
DOI : 10.1137/1.9781611974331.ch80
URL : http://arxiv.org/abs/1509.03990

S. Gaspers, N. Misra, S. Ordyniak, S. Szeider, and S. , Backdoors into heterogeneous classes of SAT and CSP, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp.2652-2658, 2014.
DOI : 10.1016/j.jcss.2016.10.007

S. Gaspers, S. Ordyniak, S. Ms-ramanujan, S. Saurabh, and . Szeider, Backdoors to q-Horn, Algorithmica, vol.35, issue.2, pp.540-557, 2016.
DOI : 10.1007/s00453-014-9958-5

S. Gaspers and S. Szeider, Kernels for global constraints, Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pp.540-545, 2011.

S. Gaspers and S. Szeider, Backdoors to Satisfaction, The Multivariate Algorithmic Revolution and Beyond, pp.287-317, 2012.
DOI : 10.1016/S0747-7171(02)00091-3
URL : http://arxiv.org/abs/1110.6387

R. Gault and P. G. Jeavons, Implementing a Test for Tractability, Constraints, vol.9, issue.2, 2004.
DOI : 10.1023/B:CONS.0000024049.41091.71

D. Geiger, Closed systems of functions and predicates, Pacific Journal of Mathematics, vol.27, issue.1, pp.95-100, 1968.
DOI : 10.2140/pjm.1968.27.95

P. Ian, B. M. Gent, and . Smith, Symmetry breaking in constraint programming, Proceedings of the Fourteenth European Conference on Artificial Intelligence, pp.599-603, 2000.

O. P. Goldreich, N. , and N. , The basics of computational complexity, 2010.

G. Gottlob, On minimal constraint networks, Proceedings of the Seventeenth International Conference on Principles and Practice of Constraint Programming, pp.325-339, 2011.
DOI : 10.1016/j.artint.2012.07.006
URL : http://arxiv.org/abs/1103.1604

J. Martin, D. A. Green, and . Cohen, Domain permutation reduction for constraint satisfaction problems, Artificial Intelligence, vol.172, issue.8-9, pp.1094-1118, 2008.

M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side [80] Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers, Journal of the ACM ACM Transactions on Algorithms, vol.54, issue.111, pp.1-244, 2007.

J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, vol.72, issue.8, pp.721386-1396, 2006.
DOI : 10.1016/j.jcss.2006.02.001
URL : http://doi.org/10.1016/j.jcss.2006.02.001

D. William, . Harvey, L. Matthew, and . Ginsberg, Limited discrepancy search, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pp.607-615, 1995.

E. Hebrard, Mistral, a Constraint Satisfaction Library, The Third International CSP Solver Competition, pp.31-40, 2008.

P. Hell and J. Ne?et?il, The core of a graph, Discrete Mathematics, vol.109, issue.1-3, pp.117-126, 1992.
DOI : 10.1016/0012-365X(92)90282-K

P. Hell and J. Ne?et?il, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.92-110, 1990.
DOI : 10.1016/0095-8956(90)90132-J

D. Hermelin and X. Wu, Weak Compositions and Their Applications to Polynomial Lower Bounds for Kernelization, Proceedings of the Twenty- Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp.104-113, 2012.
DOI : 10.1137/1.9781611973099.9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.230.7757

J. H. Marijn, O. Heule, V. W. Kullmann, and . Marek, Solving and verifying the boolean pythagorean triples problem via cube-and-conquer, Proceedings of the Nineteenth International Conference Theory and Applications of Satisfiability Testing, 2016.

E. John, R. M. Hopcroft, and . Karp, An n 5/2 Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing, vol.2, issue.4, pp.225-231, 1973.

F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier, Fixed-Parameter Algorithms for??Cluster Vertex Deletion, Theory of Computing Systems, vol.144, issue.1???2, pp.196-217, 2010.
DOI : 10.1007/s00224-008-9150-x

M. Pawel, P. Idziak, R. Markovic, M. Mckenzie, R. Valeriote et al., Tractability and learnability arising from algebras with few subpowers, SIAM Journal on Computing, vol.39, issue.7, pp.3023-3037, 2010.

Y. Iwata, M. Wahlström, and Y. Yoshida, Half-integrality, LP-branching, and FPT Algorithms, SIAM Journal on Computing, vol.45, issue.4, pp.1377-1411, 2016.
DOI : 10.1137/140962838

G. Peter and . Jeavons, On the algebraic structure of combinatorial problems, Theoretical Computer Science, vol.200, pp.185-204, 1998.

G. Peter, D. A. Jeavons, M. C. Cohen, and . Cooper, Constraints, consistency and closure, Artificial Intelligence, vol.101, issue.12, pp.251-265, 1998.

G. Peter, D. A. Jeavons, M. Cohen, and . Gyssens, Closure properties of constraints, Journal of the ACM, vol.44, issue.4, 1997.

G. Peter, M. C. Jeavons, and . Cooper, Tractable constraints on ordered domains, Artificial Intelligence, vol.79, issue.2, pp.327-339, 1995.

P. Jégou, S. Ndojh-ndiaye, and C. Terrioux, Dynamic heuristics for backtrack search on tree-decomposition of csps, Proceedings of the Twentieth International Joint Conference on Artifical Intelligence, pp.112-117, 2007.

N. Jussien and O. Lhomme, Local search with constraint propagation and??conflict-based heuristics, Artificial Intelligence, vol.139, issue.1, pp.21-45, 2002.
DOI : 10.1016/S0004-3702(02)00221-7
URL : https://hal.archives-ouvertes.fr/hal-00869124

R. M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

G. Katsirelos, Nogood processing in CSPs, 2008.

M. Kozik, Weak consistency notions for all the CSPs of bounded width, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, pp.633-641, 2016.
DOI : 10.1145/2933575.2934510

M. Kozik, A. Krokhin, M. Valeriote, and R. Willard, Characterizations of several Maltsev conditions. Algebra universalis, pp.205-224, 2015.

S. Kratsch, A randomized polynomial kernelization for vertex cover with a smaller parameter, Proceedings of the Twenty-Fourth Annual European Symposium on Algorithms, pp.1-5917, 2016.

S. Kratsch and M. Wahlström, Representative Sets and Irrelevant Vertices: New Tools for Kernelization, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp.450-459, 2012.
DOI : 10.1109/FOCS.2012.46
URL : http://arxiv.org/abs/1111.2195

M. Kronegger, S. Ordyniak, and A. Pfandler, Backdoors to planning, Proceedings of the Twenty-Eigth AAAI Conference on Artificial Intelligence, pp.2300-2307, 2014.

M. Kronegger, S. Ordyniak, and A. Pfandler, Variabledeletion backdoors to planning, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp.3305-3312, 2015.

R. E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM, vol.22, issue.1, pp.155-171, 1975.
DOI : 10.1145/321864.321877

M. Lampis, A kernel of order for vertex cover, Information Processing Letters, vol.111, issue.23-24, pp.1089-1091, 2011.
DOI : 10.1016/j.ipl.2011.09.003

C. Benoit-larose, C. Loten, and . Tardif, A characterisation of first-order constraint satisfaction problems, Logical Methods in Computer Science, vol.3, issue.4, 2007.

M. John, M. Lewis, and . Yannakakis, The node-deletion problem for hereditary properties is NP-complete, Journal of Computer and System Sciences, vol.20, issue.2, pp.219-230, 1980.

A. K. Mackworth, Consistency in networks of relations, Artificial Intelligence, vol.8, issue.1, pp.99-118, 1977.
DOI : 10.1016/0004-3702(77)90007-8

A. K. Mackworth, On reading sketch maps, Proceedings of the Fifth International Joint Conference on Artificial Intelligence, pp.598-606, 1977.

M. Maher, N. Narodytska, C. Quimper, and T. Walsh, Flow-Based Propagators for the SEQUENCE and Related Global Constraints, Proceedings of the Fourteenth International Conference on Principles and Practice of Constraint Programming, pp.159-174, 2008.
DOI : 10.1007/978-3-540-85958-1_11
URL : http://arxiv.org/abs/0909.4452

U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences, vol.7, pp.95-132, 1974.
DOI : 10.1016/0020-0255(74)90008-5

W. Matthew, . Moskewicz, F. Conor, Y. Madigan, L. Zhao et al., Chaff: Engineering an efficient sat solver, Proceedings of the 38th annual Design Automation Conference, pp.530-535, 2001.

A. El and M. , Tractable Classes of Constraint Satisfaction Problems: From Theory to Practice, 2014.

L. George, . Nemhauser, E. Leslie, and . Trotter-jr, Vertex packings: structural properties and algorithms, Mathematical Programming, pp.232-248, 1975.

N. Nishimura, P. Ragde, and S. Szeider, Detecting backdoor sets with respect to horn and binary clauses, Proceedings of the Seventh International Conference on Theory and Applications of Satisfiability Testing, pp.96-103, 2004.

E. L. Post, The two-valued iterative systems of mathematical logic, Annals Mathematical Studies, vol.5, 1941.
DOI : 10.1515/9781400882366

I. Razgon, O. Barry, and . Sullivan, Almost 2-SAT is fixed-parameter tractable, Journal of Computer and System Sciences, vol.75, issue.8, pp.435-450, 2009.
DOI : 10.1016/j.jcss.2009.04.002
URL : http://doi.org/10.1016/j.jcss.2009.04.002

B. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Operations Research Letters, vol.32, issue.4, pp.299-301, 2004.
DOI : 10.1016/j.orl.2003.10.009
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6357

J. Régin, Global Constraints: A Survey, Hybrid optimization, pp.63-134, 2011.
DOI : 10.1007/978-1-4419-1644-0_3

N. Robertson and P. D. Seymour, Graph Minors .XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995.
DOI : 10.1006/jctb.1995.1006
URL : http://doi.org/10.1006/jctb.1999.1919

Y. Ruan, A. Henry, E. Kautz, and . Horvitz, The backdoor key: A path to understanding problem hardness, Proceedings of the Nineteenth National Conference on Artificial Intelligence, pp.118-123, 2004.

Y. Saad, Iterative methods for sparse linear systems, Siam, 2003.
DOI : 10.1137/1.9780898718003

M. Samer and S. Szeider, Backdoor trees, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, pp.13-17, 2008.

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.216-226, 1978.
DOI : 10.1145/800133.804350

H. Mark and . Siggers, A strong mal'cev condition for locally finite varieties omitting the unary type, Algebra universalis, vol.64, issue.12, pp.15-20, 2010.

L. Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, vol.5, issue.3, pp.19-25, 1973.
DOI : 10.1145/1008293.1008294

S. Szeider, Backdoor Sets for DLL Subsolvers, Journal of Automated Reasoning, vol.13, issue.7, pp.73-88, 2005.
DOI : 10.1007/s10817-005-9007-9

C. Balder-ten and V. Dalmau, The product homomorphism problem and applications, Proceedings of the Eighteenth International Conference on Database Theory, 2015.

P. Van-beek and R. Dechter, On the minimality and global consistency of row-convex constraint networks, Journal of the ACM, vol.42, issue.3, pp.543-561, 1995.
DOI : 10.1145/210346.210347

R. Willard, Testing Expressibility Is Hard, Proceedings of the Sixteenth International Conference on Principles and Practice of Constraint Programming, pp.9-23, 2010.
DOI : 10.1007/978-3-642-15396-9_4

R. Williams, C. P. Gomes, and B. Selman, Backdoors to typical case complexity, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pp.1173-1178, 2003.