R. Ganian, M. S. Ramanujan, S. Szeider:

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

ACM Transactions on Algorithms,13(2017), 1 - 31.

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 article 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 is not 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, that is, 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

time f (k)nO(1) a strong backdoor into a scattered class (associated

with a list of finite conservative constraint languages) of size k or

correctly decides that there is not 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.

http://dx.doi.org/10.1145/3014587

https://dl.acm.org/citation.cfm?doid=3040971.3014587

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