R. Ganian:

"Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting";

Talk: Contemporary Trends in Theoretical Computer Science 2015, Prag, Tschechien (invited); 2015-06-26 - 2015-06-27.

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 CSP can be solved in polynomial time; such classes are

often called "islands of tractability". A prominent way of

defining islands of tractability for CSP is to restrict the

relations that may occur in the constraints to a fixed set, called a

constraint language, whereas 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 conservative

constraint languages.

This paper addresses the general limit of the mentioned tractability

results for CSP and #CSP, that they only apply to instances

where all constraints belong to a single tractable language (in

general, the union of two tractable languages isn't tractable). We

show that we can overcome this limitation as long as we keep some

control of how constraints over the various considered tractable

languages interact with each other. For this purpose we utilize the

notion of a strong backdoor of a CSP instance, as introduced

by Williams et al. (IJCAI 2003), which is a set of variables that

when instantiated moves the instance to an island of tractability,

i.e., to a tractable class of instances. We consider strong

backdoors into scattered classes, consisting of CSP instances

where each connected component belongs entirely to some class from a

list of tractable classes. Figuratively speaking, a scattered class

constitutes an archipelago of tractability. The main difficulty

lies in finding a strong backdoor of given size k; once it 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 component wise. Our main

result is an algorithm that, given a CSP instance with $n$

variables, finds in FPT time a strong backdoor into

a scattered class (associated with a list of finite conservative

constraint languages) of size k or correctly decides that there

isn't such a backdoor.

This also gives the running time for solving #CSP, provided that

#CSP is polynomial-time tractable for the considered

constraint languages. Our result makes significant progress towards the main goal of the backdoor-based approach to CSPs - the identification of maximal base classes for which small backdoors can be detected efficiently.

Created from the Publication Database of the Vienna University of Technology.