Title: The Constraint Satisfaction Problem: Complexity and Approximability
Editors: Andrei Krokhin and Stanislav Živný
Series: DFU (Dagstuhl Follow-Ups)
Volume: 7
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl
Publishing
Publication Date: February, 2017
ISBN: 978-3-95977-003-3
== Open Access ==
Accessible online and free of charge at
http://www.dagstuhl.de/dagpub/978-3-95977-003-3
You may also check the DBLP entry at
http://www.dblp.org/db/conf/dagstuhl/dfu7.html
== About the Book ==
The constraint satisfaction problem (CSP) provides a unifying framework
in which it is possible to express a wide variety of computational
problems dealing with mappings and assignments, including
satisfiability, graph colourability, and systems of equations. The CSP
framework originated independently in artificial intelligence (AI),
database theory, and graph theory, under three different guises, and it
was realised only in the late 1990s that these are in fact different
faces of the same fundamental problem. Nowadays, the CSP is extensively
used in theoretical computer science, being a mathematical object with
very rich structure that provides an excellent laboratory both for
classification methods and for algorithmic techniques.
An instance of CSP consists of a set of variables, a set of values for
the variables, and a set of constraints that restrict the combinations
of values that certain subsets of variables may take. Given such an
instance, the possible questions include (a) deciding whether there is
an assignment of values to the variables so that every constraint is
satisfied, or optimising such assignments in various ways, (b) counting
satisfying assignments, exactly or approximately, or (c) finding an
assignment satisfying as many constraints as possible.
Constraint satisfaction has always played a central role in
computational complexity theory and it is only natural that CSPs play a
role in many high-profile conjectures in complexity theory, exemplified
by the Dichotomy Conjecture of Feder and Vardi and the Unique Games
Conjecture of Khot.
The Dagstuhl Seminar 15301 "The Constraint Satisfaction Problem:
Complexity and Approximability" brought together 43 researchers from
different highly advanced areas of constraint satisfaction and involved
many specialists who use universal-algebraic, combinatorial, geometric
and probabilistic techniques to study CSP-related algorithmic problems.
For some of the topics presented at the seminar there are excellent
surveys. Some other topics are still too nascent to justify survey
articles at this point. For several topics for which no surveys
presently exist or the current ones are already outdated due to the
recent progress, we felt that the time is ripe to produce such surveys
as a follow-up to the Dagstuhl Seminar 15301.
== Table of Contents ==
1. Polymorphisms, and How to Use Them. Libor Barto and Andrei Krokhin
and Ross Willard
2. Absorption in Universal Algebra and CSP. Libor Barto and Marcin Kozik
3. Constraint Satisfaction Problems over Numeric Domains. Manuel
Bodirsky and Marcello Mamino
4. Hybrid Tractable Classes of Constraint Problems. Martin C. Cooper and
Stanislav Živný
5. Backdoor Sets for CSP. Serge Gaspers, Sebastian Ordyniak, and Stefan
Szeider
6. On the Complexity of Holant Problems. Heng Guo and Pinyan Lu
7. Parameterized Constraint Satisfaction Problems: a Survey. Gregory
Gutin and Anders Yeo
8. Counting Constraint Satisfaction Problems. Mark Jerrum
9. The Complexity of Valued CSPs. Andrei Krokhin and Stanislav Živný
10. Algebra and the Complexity of Digraph CSPs: a Survey. Benoît Larose
11. Approximation Algorithms for CSPs. Konstantin Makarychev and Yury
Makarychev
12. Quantified Constraints in Twenty Seventeen. Barnaby Martin
See also:
* Frontmatter incl. table of contents and preface:
http://dx.doi.org/10.4230/DFU.Vol7.15301.i
* CompleteVolume-PDF (7 MB):
http://drops.dagstuhl.de/opus/volltexte/dfu-complete/dfu-vol7-complete.pdf
== About the Dagstuhl Follow-Ups Series ==
The Dagstuhl Follow-Ups (DFU) series is a publication series which
offers a frame for the publication of peer-reviewed paper collections
based on Dagstuhl Seminars. DFU volumes are published according to the
principle of OpenAccess, i.e., they are available online and free of
charge.
See also:
* http://www.dagstuhl.de/dfu
* http://drops.dagstuhl.de/dfu
--
Dr. Marc Herbstritt
Scientific Staff | \\\/ Dagstuhl Publishing
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
http://www.dagstuhl.de/herbstritt
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
