Discovering Archipelagos of Tractability: Split-Backdoors to Constraint Satisfaction

ABSTRACT. The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which the CSP can be solved in polynomial time, such classes are often called "islands of tractability". A prominent way of defining islands of tractability for the CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language. A constraint language is conservative if it contains all unary relations. Schaefer's famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values. Since then many extensions and generalizations of this result have been obtained.

Recently, Bulatov (TOCL 2011, JACM 2013) gave a full characterization of all islands of tractability for CSP and the counting version CSP that are defined in terms of a conservative constraint language. Our results build upon these results and show how the identified islands of tractability can be combined to "archipelagos of tractability" (in general, the union of tractable constraint languages is not tractable). In order to put this to work, we need some control over the way how the constraints over the various considered tractable languages interact with each other. We capture this by the notion of a split-backdoor which is a set of variables that, when instantiated, separate the CSP instance into pairwise independent parts, each of which falls into a different island of tractability. Strong backdoors, as introduced by Williams et al. (IJCAI 2003), form the special case where all instantiations of the backdoor variables move the instance into one fixed island.

The main difficulty lies in finding a split-backdoor of given size k; once the split-backdoor is found, we can try all possible instantiations of the backdoor variables and apply the polynomial time algorithms associated with the islands of tractability on the list. Our main result is an algorithm that finds a split-backdoor (with respect to a list of finite conservative constraint languages) in FPT time; this also gives an FPT time algorithm for solving the decision or counting version of CSP for the given instance, assuming the decision or counting version of CSP, respectively, is polynomial-time tractable for the considered constraint languages.

As part of our algorithm for finding the split-backdoors, we first develop an algorithm to compute "split-modulators" in a graph theoretical setting. This has the advantage that we can build upon existing advanced algorithmic techniques. In particular, we show that for any finite collection of finite sets of (possibly disconnected) graphs F, there is an algorithm that, given a graph G and a positive integer k, in FPT time (parameterized by k) either finds a subset X of V(G) of size at most k such that for each connected component C of G-X there is some F_i in F such that C has no graph from F_i as an induced subgraph, or correctly reports that no such set X exists. This result has numerous applications outside CSP, as it can be used to combine known polynomial time algorithms for NP-hard problems restricted to classes of instances characterized by forbidden induced subgraphs.