[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



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


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1137/1.9781611974331.fm


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