ABSTRACT. We survey fixed-parameter tractability results appearing in the context of satisfiability and constraint satisfaction. The focus of the talk is on explaining the different type of questions that can be asked and briefly summarizing the known results, without going into technical details.

ABSTRACT. Connection matrices for graphs and hypergraphs are a generalization of Hankel matrices for words. They were used by L. Lovasz and A. Schrijver and their collaborators to characterize which graph parameters arise from partition functions. Lovasz also noted that they can be used to make Courcelle's Theorem, which shows that graph properties definable in Monadic Second Order Logic (MSOL) are in FPT on graph classes of bounded tree-width, logic-free by replacing MSOL-definability by a finiteness condition on the rank of connection matrices and allowing graph parameters with values in a field. In this paper we extend this to graph parameters with values in a tropical semi-rings rather than a field, and graph classes of bounded clique-width.

ABSTRACT. The class CNF(2) of CNF-formulas in which every variable has at most two occurrences is a lesser known tractable case of SAT. Backdoor sets for this class are studied in terms of parameterized complexity. The question whether there exist a CNF(2)-backdoor set of size k is hard for the class W[2], for both weak and strong backdoors, and in both cases it becomes fixed-parameter tractable when restricted to inputs in d-CNF for a fixed d.

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.

ABSTRACT. This talk is based on the published paper [Aschinger, Drescher, Gottlob, Jeavons, and Thorstensen, STACS 2011]. We review structural problem decomposition methods, such as tree and path decompositions. It is argued that these notions can be applied in two distinct ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. Examples are given for both cases, and the refined taxonomy below is illustrated. When we speak about the treewidth of a problem instance, we mean the treewidth of some graph associated with the instance. Obviously, for each concrete problem, one has to indicate what this graph is, and, whenever necessary, how it can be obtained from the instance.

Taxonomy:
1. Proving a problem tractable for instances of bounded treewidth  1.a General tractability results
  1.b Fixed-parameter tractability results
2. Using treewidth as a tool for proving a problem to be generally tractable (on all instances)
  2.a Proving that a problem is tractable both for small and large treewidth
  2.b Proving that all yes-instances of a problem have bounded treewidth and that the problem is tractable for this reason

ABSTRACT. Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class. The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research.

In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find.

We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits.

Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.