T.: Detecting and exploiting subproblem tractability

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 poly-nomial membership testing algorithms, to check if a language is closed under a majority or conser-vative 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 experimen-tal results on the XCSP benchmark set. We identi-fied a few promising problem classes where prob-lems were nearly closed under a majority polymor-phism and small backdoors could be computed.