Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Lists
Only you see this
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. 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 \emph{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. In this paper, we consider strong backdoors into \emph{scattered classes}, consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Our main result is an algorithm that, given a CSP instance with $n$ variables, finds in time $f(k)n^{O(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.
BibTeX
@inproceedings{ganian2016discovering,
author = {Robert Ganian and M. S. Ramanujan and Stefan Szeider},
title = {{Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting}},
booktitle = {SODA},
year = {2016},
doi = {10.1137/1.9781611974331.ch114},
}| Combining Treewidth and Backdoors for CSP | arXiv · 2016 |
| Backdoors into Heterogeneous Classes of SAT and CSP | arXiv · 2015 |
| On Backdoors To Tractable Constraint Languages | arXiv · 2014 |
| Amalgams of Constraint Satisfaction Problems | IJCAI · 2003 |
| Constraint Satisfaction, Databases, and Logic | IJCAI · 2003 |
| The Parameterized Complexity of Global Constraints | arXiv · 2009 |