<div class="csl-bib-body">
<div class="csl-entry">Ganian, R., Ramanujan, M. S., & Szeider, S. (2016). Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. In R. Krauthgamer (Ed.), <i>Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1670–1681). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974331.ch114</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/55439
-
dc.description.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.
en
dc.language.iso
en
-
dc.title
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
-
dc.relation.isbn
9781611974331
-
dc.relation.doi
10.1137/1.9781611974331
-
dc.description.startpage
1670
-
dc.description.endpage
1681
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
-
tuw.relation.publisher
Society for Industrial and Applied Mathematics
-
tuw.relation.publisherplace
Philadelphia, PA
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1137/1.9781611974331.ch114
-
dc.description.numberOfPages
12
-
tuw.event.name
ACM-SIAM Symposium on Discrete Algorithms (SODA)
en
tuw.event.startdate
01-01-2016
-
tuw.event.enddate
01-01-2016
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Austin
-
tuw.event.country
US
-
tuw.event.presenter
Ramanujan, M. Sridharan
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.presentation.type
science to science/art to art
-
item.fulltext
no Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.grantfulltext
none
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity