https://www.dagstuhl.de/18231

### June 3 – 8 , 2018, Dagstuhl Seminar 18231

# The Constraint Satisfaction Problem: Complexity and Approximability

## Organizers

Martin Grohe (RWTH Aachen, DE)

Venkatesan Guruswami (Carnegie Mellon University – Pittsburgh, US)

Dániel Marx (Hungarian Academy of Sciences – Budapest, HU)

Stanislav Živný (University of Oxford, GB)

## For support, please contact

## Documents

Dagstuhl Report, Volume 8, Issue 6

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## Summary

The *constraint satisfaction problem*, or CSP in short, provides a unifying framework in which it is possible to express, in a natural way, a wide variety of computational problems dealing with mappings and assignments, including satisfiability, graph colourability, and systems of equations. The CSP framework originated 30-35 years ago independently in artificial intelligence, 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; while in AI and more applied areas of computer science, this framework is widely regarded as a versatile and efficient way of modelling and solving a variety of real-world problems, such as planning and scheduling, software verification, and natural language comprehension, to name just a few.
An instance of the 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, or (b) finding an assignment satisfying as many constraints as
possible. There are many important modifications and extensions of this basic
framework, e.g., those that deal with counting assignments or involve soft or
global constraints.

Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a weak logic). One of the most striking features of this research direction is the variety of different branches of mathematics (including universal algebra and logic, combinatorics and graph theory, probability theory and mathematical programming) that are used to achieve deep insights in the study of the CSP. In the last decade, research activity in this area has significantly intensified and hugely impressive progress was made.

The recent flurry of activity on the topic of the seminar is witnessed by four previous Dagstuhl seminars, titled "Complexity of constraints" (06401) and "The CSP: complexity and approximability" (09441, 12541, 15301), that were held in 2006, 2009, 2012, and 2015 respectively. This seminar was a follow-up to the 2009, 2012, and 2015 seminars. Indeed, the exchange of ideas at the 2009, 2012, and 2015 seminars has led to ambitious new research projects and to establishing regular communication channels. There is clearly the potential for further systematic interaction that will keep on cross-fertilising the areas and opening new research directions. The 2018 seminar brought together 47 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. The participants presented, in 24 talks, their recent results on a number of important questions concerning the topic of the seminar. One particular feature of this seminar is a significant increase in the number of talks involving multiple subareas and approaches within its research direction - a definite sign of the growing synergy, which is one of the main goals of this series of seminars.

**Concluding remarks and future plans:** The seminar was well received as witnessed by the high rate of accepted
invitations and the great degree of involvement by the participants. Because of
a multitude of impressive results reported during the seminar and active
discussions between researchers with different expertise areas, the organisers
regard this seminar as a great success. With steadily increasing interactions
between such researchers, we foresee another seminar focusing on the interplay
between different approaches to studying the complexity and approximability of
the CSP. Finally, the organisers wish to express their gratitude to the
Scientific Directors of the Dagstuhl Centre for their support of the seminar.

### Description of the Topics of the Seminar

**Classical computational complexity of CSPs.** Despite the provable existence of intermediate problems (say, between P and NP-complete, assuming P =/ NP), research in computational complexity has produced a widely known informal thesis that "natural problems are almost always complete for standard complexity classes". CSPs have been actively used to support and refine this thesis. More precisely, several restricted forms of the CSP have been investigated in depth. One of the main types of restrictions is the *constraint language* restriction, i.e. a restriction on the available types of constraints. By choosing an appropriate constraint language, one can obtain many well-known computational problems from graph theory, logic, and algebra. The study of the constraint language restriction was driven by the CSP *Dichotomy Conjecture* of Feder and Vardi which states that,
for each fixed constraint language, the corresponding CSP is either in P or NP-complete. There are similar dichotomy conjectures concerning other complexity classes (e.g., L and NL). Recent breakthroughs in the complexity of the CSP have been made possible by the introduction of the universal-algebraic approach, which extracts algebraic structure from the constraint language
and uses it to analyse problem instances. The above conjectures have algebraic versions which also predict in algebraic terms where the boundary between
harder problems and easier problems lies. The algebraic approach has been applied to prove the Dichotomy Conjecture in many important special cases (e.g., Bulatov's dichotomy theorems for 3-valued and conservative CSPs),
culminating in two independent proofs of the general conjecture announced in 2017 by Bulatov and Zhuk.

- Bulatov and Zhuk gave detailed talks on the main insights into their proofs.
- Kolmogorov described an algorithm for Boolean CSPs under the restriction that every variable appears in exactly two constraints and all constraints are even Delta-matroids.

The valued CSP (VCSP) is a significant generalisation of the CSP that involves both feasibility and optimisation aspects. While the computational complexity of finite-domain VCSPs is by now well understood, the infinite-domain VCSPs are fairly unexplored.

- Viola gave a talk on submodular VCSPs on infinite domains.
- Kazda presented his results on the structure of weighted clones, which are intimately related to the computational complexity of VCSPs.

**Approximability of CSPs.**
The use of approximation algorithms is
one of the most fruitful approaches to coping with NP-hardness.
Hard optimisation problems, however, exhibit diverse behavior
with respect to approximability, making it an exciting research area that is
by now well-developed but far from fully understood.

An emerging topic bridging the complexity of the CSP with approximation aspects
is *promise constraint satisfaction* (PCSP). The PCSP is a generalization of the CSP in which the constraints come in pairs of "stricter" and "weaker" versions. In a PCSP instance, the task is to find an assignment satisfying the weaker constraints under the promise that there is an assignment satisfying the strict constraints.

- Brakensiek gave an introductory talk to this exciting research direction and also presented a dichotomy classification for symmetric Boolean PCSPs.
- Oprsal explained the very recently introduced algebraic approach to the computational complexity of PCSPs.
- Barto presented his results on PCSPs and cyclic operations.

Many approximation algorithms for CSPs are based on convex relaxations.

- Berkholz gave an overview on relaxations for Boolean CSPs based on algebraic methods.
- Schramm explained the power of semidefinite programming relaxations for random CSPs.
- Tulsiani presented results on the limits of linear programming relaxations for CSPs.
- Makarychev showed how to obtain an integrality gap for the Calinescu-Karloff-Rabani linear programming relaxation of the Multiway-Cut problem.
- Austrin established the currently best known inapproximability result for Min UnCut, which is a special Boolean CSP.

Some of the most exciting developments in approximability in the last decade
revolve around the *unique games conjecture*, or UGC, of Khot (2002). This bold conjecture asserts that, for CSPs with a certain constraint language over a large enough domain, it is NP-hard to distinguish almost satisfiable instances from those where only a small fraction of constraints can be satisfied. This conjecture is known to imply tight inapproximability results for many classical optimisation problems. Moreover, if the UGC is true, then, as shown by Raghavendra in 2008, a simple algorithm based on semidefinite
programming provides the best possible approximation for *all* CSPs (though the exact quality of this approximation is unknown).

- Moshkovitz presented recent developments on the so-called 2-to-2 PCP theorem, which covers important special cases of the UGC.

**Logic and the complexity of CSPs.** Logic has been used in two distinct ways in the study of the CSP. One of them, starting from earlier work of Kolaitis and Vardi, is *descriptive complexity*, where one tries to classify CSPs as classes of instances with respect to definability in a given logic. The other way is to use logic to specify CSP instances, which can be done very naturally. The latter direction leads to generalisations such as the quantified CSP (QCSP), as well as to the study of CSPs over infinite domains, where important links with the algebraic approach were found.

- Roy presented a dichotomy theorem for the inverse satisfiability problem.
- Bodirsky gave a talk on two methods of reducing infinite-domain CSPs to finite-domain CSPs.
- Pinsker explained recent results on the algebraic approach to infinite-domain CSPs. These results are related to the so-called loop conditions, which were in more detail discussed by Kozik.
- Kompatscher presented a proof of the equivalence of two dichotomy conjectures for infinite-domain CSPs.
- Mottet gave a new proof of the dichotomy for MMSNP and discussed consequences for infinite-domain CSPs.
- Martin described recent results for temporal and spatial problems, which are special cases of infinite-domain CSPs.

**Exact exponential complexity of CSPs.**
The area of parameterised complexity is closely related to the area of exact
exponential complexity, in which the goal is to design the most efficient
exponential-time algorithms. There has been significant progress on the exact
exponential complexity of CSPs.

- Golovnev presented results that give optimal lower bounds on the running time of algorithms for deciding if there is a homomorphism from one graph to another.
- The complexity of counting solutions for CSPs and related problems from statistical physics were presented by Goldberg and Jerrum.

**Summary text license**

Creative Commons BY 3.0 Unported license

Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný

## Dagstuhl Seminar Series

- 15301: "The Constraint Satisfaction Problem: Complexity and Approximability" (2015)
- 12451: "The Constraint Satisfaction Problem: Complexity and Approximability" (2012)
- 09441: "The Constraint Satisfaction Problem: Complexity and Approximability" (2009)
- 06401: "Complexity of Constraints " (2006)

## Classification

- Data Structures / Algorithms / Complexity

## Keywords

- Constraint satisfaction problem (CSP)
- Computational complexity
- CSP dichotomy conjecture
- Hardness of approximation
- Unique games conjecture
- Parameterized complexity
- Descriptive complexity
- Universal algebra
- Logic
- Semidefinite programming