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

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

Talk: ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA; 2016-01-10 - 2016-01-12; in: "Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms", (2016), ISBN: 978-1-61197-433-1; 1670 - 1681.

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 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 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.

http://dx.doi.org/10.1137/1.9781611974331.fm

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