The Constraint Satisfaction Problem: Complexity and Approximability

Following the two independent proofs of the finite-domain CSP dichotomy in 2017 by Bulatov and Zhuk, the research in the area of constraint satisfaction problems focuses on various generalizations of the CSP framework and on uniformizing the approaches to these variants of CSPs. We list the concrete topics of the talks in the seminar below.

We introduce the concept of usefulness for PCSPs. A promise A is said to be useful if PCSP(A,B) is tractable for some non-trivial B. We then initiate investigations of this notion, focusing on the setting of folded Boolean PCSPs. This exploration leads us to revisit and generalize the “(2+eps)-Sat” problem.

While we do not obtain complete characterizations, we are able to characterize all but a tiny fraction of promises. Perhaps surprisingly, this is achieved using existing general algorithms and hardness results, and the main technical challenge is to prove that those results are applicable.

Along the way we encounter a number of curious concrete Boolean PCSPs which can serve as challenges for pushing existing algorithms and hardness criteria further.

Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs.

To every valued promise CSP we associate an algebraic object, its so-called valued minion. Our main result shows that the existence of a homomorphism between the associated valued minions implies a polynomial-time reduction between the original CSPs. We also show that this general reduction theorem includes important inapproximability results, for instance, the inapproximability of almost solvable systems of linear equations beyond the random assignment threshold.

This tutorial explores past and recent advances in understanding the approximability of Max-CSPs. In the first tutorial, I will discuss the approximation algorithms and the known hardness of approximation results. In the second tutorial, I will go over Raghavendra’s characterization of the approximability of almost satisfiable Max-CSPs. Finally, in the last tutorial, I will discuss the recent work on the approximability of satisfiable CSPs including the hybrid algorithm that combines SDP rounding and Gaussian elimination algorithms in a non-trivial way. Inverse theorems are the theorem statements that find a structure on correlated functions. I will discuss the statement of the inverse theorems for 3-ary correlations and how to use them in the analysis of the hybrid algorithm.

As powerful as algebraic methods are for finite-domain CSPs, they exhibit challenges to be generalised for infinite, countably categorical structures. Rather than lifting the algebraic notions tailored for finite algebras, it is often easier to extend combinatorial constructions to the infinite setting. The broader goal, therefore, is to recast known finite structural dichotomies as combinatorial proofs that can then be lifted to the countably categorical case. Pursuing this programme, we overcome previous obstacles to lifting structural results for digraphs in this context from the finite to the omega-categorical realm – the strongest lifting results hitherto not going beyond a generalisation of the Hell-Nešetřil theorem for undirected graphs.

A celebrated result of Håstad established that, for any constant $\epsilon >0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\epsilon )$-fraction of the constraints of a given 3-LIN instance over an Abelian group G even if one is promised that an assignment satisfying a $(1-\epsilon )$-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.

In this talk, I review work on the hardness of defining the approximation of optimization problems in a logic such as fixed-point logic with counting (FPC), which corresponds to a natural symmetric fragment of P. Decision problems in FPC include those solvable by linear and semidefinite programming, yet we are able to show unconditional lower bounds against it. In recent work with Bálint Molnár, we establish the undefinability of approximation of 2-to-2 games by showing that no FPC class separates the satisfiable instances from those that are no more than epsilon-satisfiable. This has significant implications for promise graph colouring problems

CSPs expressible in guarded monotone strict NP (GMSNP) remain one of the most prominent open cases within the scope of the Bodirsky-Pinsker conjecture about infinite-domain CSPs. A conjecture of Brakensiek and Guruswami about promise CSPs implies that if G is an infinite non-bipartite graph with finite chromatic number, then CSP(G) is NP-hard. In this talk we are interested in the interplay between CSPs expressible in GMSNP and promise CSPs. We will we see that for every template S of a CSP expressible in GMSNP, there is a finite-domain “approximation” C of its CSP. Using this approximation we show the following.
1) If G is a non-bipartite graph with finite chromatic number whose CSP is in GMSNP, then CSP(G) is NP-complete.
2) If the tractability of a finite-template PCSP is explained by a GMSNP sandwich, then it is also explained by a finite sandwich.

Ramsey’s theorem and Kőnig’s tree lemma are two famous combinatorial results from the early 20th century, the former talks about colouring subsets of finite sets, while the latter is more akin to a choice principle, allowing us to find infinite paths within trees. At first glance they seem unrelated, though they share one moral similarity: both establish order within seemingly chaotic, infinite objects. We make this precise, by proving that a generalized Kőnigs lemma holds on a category if and only if it has the Ramsey property.

I will present a method to reduce extremal combinatorial problems to establishing the unsatisfiability of k-sparse linear equations mod 2 (aka k-XOR CSP) with a limited amount of randomness. This latter task is then accomplished by bounding the spectral norm of certain “Kikuchi” matrices built from the k-XOR formulas. In these talks, I will discuss a couple of applications of this method from the following list.

1. 1.

   Proving hypergraph Moore bound (Feige’s 2008 conjecture) – the optimal trade-off between the number of equations in a system of k-sparse linear equations modulo 2 and the size of the smallest linear dependent subset. This theorem generalizes the famous irregular Moore bound of Alon, Hoory and Linial (2002) for graphs (equivalently, 2-sparse linear equations mod 2).

2. 2.

   Proving a cubic lower bound on 3-query locally decodable codes (LDCs), improving on a quadratic lower bound of Kerenedis and de Wolf (2004) and its generalization to q-query locally decodable codes for all odd q,

3. 3.

   Proving an exponential lower bound on linear 3-query locally correctable codes (LCCs). This result establishes a sharp separation between 3-query LCCs and 3-query LDCs that are known to admit a construction with a sub-exponential length. It is also the first result to obtain any super-polynomial lower bound for >2-query local codes.

Time permitting, I may also discuss applications to strengthening Szemeredi’s theorem, which asks for establishing the minimal size of a random subset of integers S such that every dense subset of integers contains a 3-term arithmetic progression with a common difference from S, and the resolution of Hamada’s 1970 conjecture on the algebraic rank of binary 4-designs.

Given a fixed arity $k\ge 2$, Min-k-CSP on complete instances is the problem whose input consists of a set of n variables V and one (nontrivial) constraint for every k-subset of variables (so there are $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ constraints), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on more general dense or expanding instances, the approximability of Min-k-CSP has not been well understood. Moreover, for some CSPs including Min-k-SAT, there is an approximation-preserving reduction from general instances to dense and expanding instances, leaving complete instances as a unique family that may admit new algorithmic techniques.

In this paper, we initiate the systematic study of Min-CSPs on complete instances. First, we present an O(1)-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since O(1)-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances.

Then we study the decision versions of CSPs, whose goal is to find an assignment that satisfies all constraints; an algorithm for the decision version is necessary for any nontrivial approximation for the minimization objective. Our second main result is a quasi-polynomial time algorithm for every Boolean k-CSP on complete instances, including Min-k-SAT. We complement this result by giving additional algorithmic and hardness results for CSPs with a larger alphabet, yielding a characterization of (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances.

In this talk, I will introduce a class of constraint satisfaction problems known as Phylogenetic Constraint Satisfaction Problems. We will consider specific examples from this class, including MaxTriplets and MaxQuarters, which are motivated by applications in computational biology and database theory. We will explore the notions of approximation resistance and biased random assignment. Finally, we will examine the relationship between phylogenetic CSPs and ordering CSPs and show that phylogenetic CSPs are approximation resistant building on the seminal result of Guruswami, Håstad, Manokaran, Raghavendra, and Charikar (2011).

We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following.

1. For Max-Cut and Max 2-Lin, we design an algorithm that yields a near-optimal solution when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees.

2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still $1/2+\eta$ hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is $1/2+\eta$ hard to approximate even when the average degree of the instance is linear in the number of variables.

Based on joint work with Suprovat Ghoshal and Konstantin Makarychev.

In recent years, much attention has be placed on the complexity of graph homomorphism problems when the input is restricted to $P_k$-(subgraph)-free graphs. We consider the directed version of this research line, by addressing the question: is it true that digraph homomorphism problems CSP($H$) have a P versus NP-complete dichotomy when the input is restricted to $D{P}_k$-(subgraph)-free digraphs (where $D{P}_k$ is the directed path on $k$ vertices)? We build on the theory of constraint satisfaction problems to address this question.

Our first main results are a P versus NP-complete classification of CSPs when the input is restricted to $ℱ$-homomorphism-free digraphs, or restricted to CSP($H^{\prime }$) for some finite digraph $H^{\prime }$. We then use the established connection to constraint satisfaction theory to show our third main result (and partial answer to the question above): if CSP($H$) is NP-complete, then there is a positive integer $N$ such that CSP($H$) remains NP-hard even for $D{P}_N$-(subgraph)-free digraphs. Moreover, CSP($H$) remains NP-hard for $D{P}_N$-(subgraph)-free acyclic digraphs, and becomes polynomial-time solvable for $D{P}_{N-1}$-(subgraph)-free acyclic digraphs.

Another contribution of this work is verifying the question above for digraphs on three vertices and a family of smooth tournaments.

In this tutorial, I give an introduction to the type of problems that are studied in the area of infinite-domain constraint satisfaction with omega-categorical templates. With a template-free approach first, I show that the finite and infinite-domain CSPs are very similar and that infinite-domain CSPs are easily motivated by certain coloring problems for graphs. In a second part, I outline some of the more recent results concerning infinite-domains CSPs, in particular the recent theory of smooth approximations, used to study questions of hardness for infinite-domain CSPs, as well as some of my recent results showing how to think about infinite-domain CSPs in terms of associated promise CSPs with finite templates.

We present a new framework of approximation problems, combining quantitative and qualitative approximation. We explore several new tractability and hardness results within this framework: maximum dicut vs. cut, maximum dicut vs. acyclic subgraph, maximum k vs. l colouring, and maximum cut vs. triangle-free subgraph.

This is joint work with Standa Živný.

The talk included some topology in an emerging new application of homotopy theory in CSPs and promise CSPs. This approach is build on the question: How does the topology of the solution space of a computational problem influence its complexity? I presented an introduction to a key notion of homomorphism complexes used in this line of work, and a brief overview of what have we done with it so far.

In MinCSP(A), we are given an instance of CSP(A), and the goal is to compute its cost, which is the minimum number of constraints violated by any assignment to its variables. For many choices of A, MinCSP(A) is notoriously hard. For example, even in the Boolean case where A consists solely of binary disequality, the Unique Games Conjecture rules out constant-factor approximation in polynomial time. We study FPT-algorithms for this problem with the natural parameter being the cost.

For every Boolean bijunctive language A, we show that there exists a constant $c=c(A)$ such that: – MinCSP(A) admits a factor-$c$ FPT-approximation, and – MinCSP(A) does not admit a factor – $(c-\epsilon )$ FPT-approximation for any $\epsilon >0$, unless the ETH is false. Note that the case with $c=1$ is equivalent to finding an exact solution, so our result refines part of the Boolean MinCSP FPT dichotomy by Kim, Kratsch, Pilipczuk and Wahlström [SODA’2023]. In fact, their FPT-algorithm with a small modification in the last step is sufficient to achieve optimal approximation factors, so our main contribution is proving matching lower bounds under the ETH. Our reduction builds upon the W[1]-hardness proof by [Marx & Razgon, IPL’2009] for, essentially, Boolean MinCSP with constant unary relations and a 4-ary relation $(a\to b)\wedge (c\to d)$. We use a generalization of k-Clique - the Densest k-Subgraph problem - combined with the recent breakthrough of Guruswami, Lin, Ren, Sun & Wu [STOC’2024] proving Parameterized Inapproximability Hypothesis under ETH and a densification result due to Bafna, Karthik & Minzer [STOC’25]. As a corollary, we obtain that several FPT-approximation algorithms in the literature achieve optimal approximation factors under the ETH.

It is well-known that finite or omega-categorical tractable CSP templates must have an essential polymorphism, i.e. a polymorphism that depends on more than one variable. In fact, it is folklore that they must have a ternary such polymorphism. Well-known examples of ternary essential polymorphisms are those satisfying the (ternary) majority or minority identities; these examples also show that in general, one cannot expect binary essential polymorphisms for tractable templates.

We report on a recent result stating that if a template is a finite or omega-categorical core, and its automorphisms do not happen to form a Boolean group acting freely, then tractability of its CSP implies the existence of a binary essential polymorphism. The proof of this result builds on a new generalization/improvement of results of Rosenberg and Bodirsky+Chen on minimal clones.

We present simple deterministic gap-producing reductions from the canonical NP-hard problem of solving systems of quadratic equations to the approximate versions of the Nearest Codeword Problem (NCP) and the Minimum Distance Problem (MDP)—achieving inapproximability within arbitrary constant factors. Our reductions and proofs are short and conceptually clean, relying primarily on linear codes in which all codewords have roughly equal weight.

The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. In this talk, I motivate several fundamental questions on the scope of the Bodirsky-Pinsker conjecture and provide answers to some of them. This concerns, e.g., identifying model-theoretic assumptions that can be added without loss of generality or finding general connections to finite-domain promise CSPs. The presented material stems from joint work with Michael Pinsker, Moritz Schöbi, and Christoph Spiess.

A recent research topic in database theory is the computational complexity of resilience of queries. For a fixed conjunctive query, the problem is to compute the number of facts that need to be removed from a given database so that it does not satisfy the query. In this talk, I will explain how resilience problems can be viewed as valued constraint satisfaction problems (VCSPs) of structures that are finite or at least finite-like (in the sense that they have an oligomorphic automorphism group). Building on the known results about VCSPs on finite domains, we explore how the setting can be generalized to infinite domains and give some general powerful hardness and tractability conditions for the resilience problem. We also present recent results for queries over a signature consisting of a single binary relation, and results on the existence and uniqueness of cores of valued structures stemming from resilience problems. This is based on joint work with Manuel Bodirsky, Colin Jahel, and Carsten Lutz.

Streaming model is one of the most successful models for solving combinatorial optimization problems involving big data. In this talk, we explore the topic of approximability of constraint satisfaction problems in the streaming model. The main theorem that we cover is a dichotomy theorem from the joint work of Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy, in the dynamic streaming model, where constraints can be added to or deleted from the stream. For any $\gamma >\beta$, consider the promise problem where the Max-CSP value is promised to be either larger than $\gamma$ or smaller than $\beta$. The dichotomy theorem states that the problem of distinguishing the promise instances can either be solved using logarithmic space or requires at least polynomial space, and gives a PSPACE characterization to decide them. This characterization is discussed in detail for the special case of Boolean CSPs and the talk concludes with some interesting open problems in this area.

Let G be a non-bipartite, 4-colorable graph. We show that it is NP-hard to distinguish between graphs that are G-colorable and graphs that are not even 4-colorable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3), 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019] and Wrochna and Živný [SODA 2020].

The proof combines the algebraic theory of promise constraint satisfaction problems developed by Barto, Bulín, Krokhin, and Opršal [J. ACM 68(4), 28:1–66 (2021)] with methods of topological combinatorics and equivariant obstruction theory.

The celebrated result of Barto, Kozik and Willard states that every finite-domain CSP with bounded strict width is in NL. We prove that the same holds for a large class of structures within Bodirsky-Pinsker conjecture. The class consists of first-order expansions of structures with finite duality with natural restrictions on the transitivity, homogeneity and algebraicity of the underlying group of automorphisms. In particular, the class contains first-order expansions of homogeneous graphs, digraphs and hypergraphs studied in the literature.

We consider singleton versions of standard universal algorithms for the (Promise) Constraint Satisfaction Problem, such as Arc Consistency, Basic Linear Programming (BLP), and Affine Integer Programming (AIP). The only difference is that, for every constraint and every tuple (or for every variable and every element of the domain), we fix the tuple, run one of the above algorithms, and rule out the value if the algorithm returns “No”. If all tuples are ruled out, we return “No”; otherwise, we return “Yes”.

The minions characterizing the power of these algorithms have been known for some time, but they were too complicated to verify the existence of a minion homomorphism. Using the Hales-Jewett theorem, we showed that the existence of a minion homomorphism is equivalent to the existence of palette block functions with certain properties. As a result, we obtained a characterization of the singleton versions of Arc Consistency, BLP, AIP, and their combinations in terms of symmetric polymorphisms of the constraint language. As a side result, we also showed that the two ways of defining singleton - by fixing a tuple of a constraint or by fixing a value for a variable - have the same power.