Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
Abstract
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are -affine -consistency, BLP+AIP, BAk, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný [10] whether a constant level of BAksolves all tractable CSPs in the negative: Indeed, not even a sublinear level suffices. We also refute a conjecture by Dalmau and Opršal [20] (LICS 2024) that every CSP is either solved by -affine -consistency or admits a Datalog reduction from 3-colorability. For the cohomological -consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template.
Keywords and phrases:
constraint satisfaction, affine relaxation, promise CSPs, -affine -consistency, cohomological -consistency algorithm, Tseitin, graph isomorphismCategory:
Track B: Automata, Logic, Semantics, and Theory of ProgrammingFunding:
Moritz Lichter: The author received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (SymSim: grant agreement No. 101054974).Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Finite Model Theory ; Theory of computation Problems, reductions and completeness ; Theory of computation Complexity theory and logicAcknowledgements:
We thank a number of people for helpful discussions and valuable input at various stages of this work, especially also for acquainting us with the problem: We are grateful to Anuj Dawar, Martin Grohe, Andrei Krokhin, Adam Ó Conghaile, Jakub Opršal, Standa Živný, and Dmitriy Zhuk. We are especially indebted to Michael Kompatscher, who kindly provided us with the proof of Theorem 2 (3).Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Constraint satisfaction problems (CSPs) provide a general framework that encompasses a huge variety of different problems, from solving systems of linear equations over Boolean satisfiability to variants of the graph isomorphism problem. We view CSPs as homomorphism problems. A CSP is defined by a relational structure called the template of the CSP. An instance is a structure of matching vocabulary and the question is whether there is a homomorphism from to . We only consider finite-domain CSPs, i.e., the template is always finite. It had long been conjectured by Feder and Vardi [23] that every finite-domain CSP is NP-complete or in P. In 2017, the conjecture was confirmed independently by Bulatov [11] and Zhuk [33]. The complexity of a CSP is determined by the polymorphisms (“higher-dimensional symmetries”) of its template. If the template has no a so-called weak near-unanimity polymorphism, then the corresponding CSP is NP-complete. For the other case, Bulatov and Zhuk presented sophisticated polynomial-time algorithms. A less involved algorithm had been known earlier for templates with a Maltsev polymorphism [12]. None of these algorithms is universal in the sense that on input they decide whether maps homomorphically into in time polynomial in both and . Instead, these are families of algorithms, one for each template. The question whether there is a universal, and ideally “simple”, algorithm for all tractable CSPs, or even just for all Maltsev CSPs, is still open.
One natural approach towards universal algorithms is via affine relaxations of systems of linear equations over : Given a template , an instance , and possibly a width parameter , the existence of a homomorphism is encoded into a system of linear equations. If the domain of the variables is relaxed from to , the system can be solved in polynomial time [27, 29], and the transformation of the CSP into the equation system is also computationally easy. Thus, if this integer relaxation was exact for all tractable CSPs, or at least an interesting subclass thereof, such as all Maltsev CSPs, then computing and solving it would constitute a universal polynomial-time algorithm for that class. Several algorithms based on this idea have been developed in recent years, motivated specifically by the study of Promise CSPs [10, 9, 17, 20]. This is a relatively new variant of CSPs which generalize for example the approximate graph coloring problem and are still not very well understood. The algorithms can be applied just the same to classical CSPs, and not even for these, much is known about their power. In the present paper, we prove strong limitations for all these algorithms and show that even for Maltsev CSPs, none of them is universal: We construct a template whose CSP is not solved by these algorithms by providing instances that admit no homomorphism to but which are accepted by the algorithms. This also refutes a conjecture by Dalmau and Opršal [20], that we expand upon below. Our result is in stark contrast to the situation for valued CSPs, an optimization version of CSP. For these, a surprisingly simple linear-algebraic algorithm solves all tractable cases optimally [31].
Let us briefly introduce the algorithms that are addressed by our construction. All of them make use of (slightly) different systems of equations, which can all be reduced to the width- affine relaxation. Given a template structure , an instance , and a width , the variables of the equation system are indexed with partial homomorphisms from induced size- substructures of to . A solution to the width- affine relaxation is thus an assignment of numerical values to partial homomorphisms. The equations enforce a consistency condition, i.e., express that partial homomorphisms with overlapping domains receive values that fit together. This is related to, but stronger than, the -consistency method: The -consistency algorithm is a well-studied simple combinatorial procedure that checks for inconsistencies between local solutions and propagates these iteratively. This solves the bounded width CSPs (see e.g. [23, 4, 2]) but is not powerful enough to deal with all tractable CSPs [1]. The consistency conditions of the width- affine relaxation are stronger in the sense that they enforce a global notion of consistency rather than a local one. The algorithms that fail to solve our counterexample are the following:
The -affine -consistency algorithm [20] (Section 5.1) runs the -consistency procedure. All non--consistent partial homomorphisms are removed from the width- affine relaxation. The algorithm accepts the instance if and only if this modified version of the width- affine relaxation has an integral solution. Dalmau and Opršal [20] conjectured that for all finite structures , is either Datalog∪-reducible to and thus solved by -affine -consistency for a fixed , or 3-colorability is Datalog∪-reducible to (see Conjecture 17). Assuming P NP, the conjecture implies that every tractable finite-domain CSP is solved by -affine -consistency.
The BLP+AIP algorithm by Brakensiek, Guruswami, Wrochna, and Živný [10] (Section 5.2) first solves the width- affine relaxation over the non-negative rationals, where is the arity of the template. Next, the integral width- affine relaxation is checked for a solution, but every variable is set to that is set to by every rational solution. The BAk-algorithm proposed by Ciardo and Živný [16] (Section 5.2) generalizes BLP+AIP: The width is not fixed to be the arity of the template but is a parameter of the algorithm, like in -affine -consistency. In [16], it is shown that there is an NP-complete (promise) CSP on which the algorithm fails, but no tractable counterexample had been known until now.
The CLAP algorithm, due to Ciardo and Živný [17] (Section 5.3), tests in the first step, for each partial homomorphism , whether can receive weight exactly in a non-negative rational solution of the width- affine relaxation, where is the arity of the template. If not, it is discarded. This is repeated until the process stabilizes. Then the width- affine relaxation is solved over the integers, where all discarded partial homomorphisms are forced to .
Theorem 1.
There is a Maltsev template with elements that is neither solved by
-
1.
-affine -consistency, for every , where is the instance size,
-
2.
BLP+AIP,
-
3.
BAk, for every , nor
-
4.
the CLAP algorithm.
Hence, none of the algorithms solves all tractable CSPs.
In particular, this answers a question of Brakensiek, Guruswami, Wrochna, and Živný [10] whether a constant level of the BAk hierarchy solves all tractable CSPs in the negative: Indeed, not even a sublinear level suffices. It also refutes the aforementioned Conjecture 17 regarding the power of the -affine -consistency relaxation [20], under the assumption that P NP. But we actually show a stronger statement: Namely, 3-colorability is not Datalog∪-reducible to the CSP that we use in the proof of the above theorem (Lemma 19). This is shown via a known inexpressibility result for rank logic [26] and disproves the conjecture unconditionally.
To prove Theorem 1, we construct and analyze instances. Our template is a combination of systems of linear equations over the Abelian groups and , but the template itself is not a group. Since the affine algorithms reduce CSPs to a problem over the infinite Abelian group , we investigate for which finite groups this is possible: we study what we call group coset-CSPs (to distinguish them from equation systems over groups). The template of a coset-CSP consists of a finite group , and its relations are cosets of powers of subgroups of . They always have a Maltsev polymorphism [6]. Coset-CSPs have been studied as “group-CSPs” by Berkholz and Grohe [6, 8] or as “subgroup-CSPs” by Feder and Vardi [23].
Theorem 2.
For each of the algorithms -affine -consistency, BLP+AIP, BAk, and CLAP, the following is true:
-
1.
Every coset-CSP over a finite Abelian group is solved (for -affine -consistency, must be at least the arity of the template structure).
-
2.
There exists a non-Abelian coset-CSP that is not solved, namely over , the symmetric group on elements (for any constant or even sublinearly growing ).
-
3.
There are non-Abelian coset-CSPs that are solved, namely over any 2-nilpotent group of odd order. For example, there are non-Abelian -nilpotent semidirect products of order for each odd prime .
While Assertion 1 is easily derived from the literature [19, 3], it turns out somewhat surprisingly that Abelian groups are not the border of tractability for the affine algorithms: They also work over certain 2-nilpotent groups; these are in a sense the non-Abelian groups that are closest possible to being Abelian. Assertion 2 is shown with a construction that is “semantically equivalent” to the one that we use for Theorem 1, but whose template is a coset-CSP. However, the analysis of the instances is technically much more involved. The construction in Theorem 1 is simpler and yields a smaller template. We show that our first counterexample can be expressed as instances of the graph isomorphism problem with bounded color class size, that is, the isomorphism problem of vertex-colored graphs, in which each color is only used for a constant number of vertices. This problem is expressible as a coset-CSP over the symmetric group [8]. This also shows that the affine CSP algorithms cannot be adapted to solve the graph isomorphism problem. They fail already on the bounded color class version, which is known to be in P [24]. There exists another highly interesting affine CSP algorithm that we have not addressed so far. This is the cohomological -consistency algorithm due to Ó Conghaile [19] (see Section 5.4). As it turns out, this algorithm is actually able to solve our counterexample correctly. Hence, for all we know, it may be possible that there is a such that cohomological -consistency is a universal polynomial-time algorithm for Maltsev or even all tractable CSPs. However, we can show without complexity-theoretic assumptions that it fails on NP-complete CSPs. Recent work by Chan and Ng [14] independently shows a similar result, but with a different technique: They prove that random instances of certain NP-complete templates are not solved by cohomological -consistency, even for , but they do not know a tractable counterexample, either.
Theorem 3.
The CSP on which the algorithms in Theorem 1 fail is solved by cohomological -consistency, for every . There exists an NP-complete CSP such that for every constant , cohomological -consistency fails to solve it.
Our Techniques.
Our proof of Theorem 1 combines results due to Berkholz and Grohe [8] with a new homomorphism or-construction that encodes the disjunction of two CSPs. For a system of linear equations to have an integral solution, it suffices to have a rational -solution and a rational -solution (for and coprime), in which all non-zero values are of the form , with , or , respectively. Thus, it suffices to design the instances in such a way that these two co-prime rational solutions exist. For the algorithms that involve a width-parameter , the additional challenge is to make the construction robust so that it works against any choice of (in our case it works even if grows with the instance size). The Tseitin contradictions [32] over expander graphs (see Section 4) achieve this robustness. It is known that these cannot be solved by “local” algorithms, e.g., the -consistency method, for any constant [1]. Berkholz and Grohe showed that the width- relaxation for unsatisfiable Tseitin contradictions over , for a prime , still has a -solution. We combine two unsatisfiable Tseitin systems over and in the aforementioned homomorphism or-construction (Section 3). This yields an unsatisfiable CSP instance whose width- relaxation has a - and a -solution and thereby also an integral solution. The reason why this approach fails for the cohomological algorithm (Theorem 3) is that it solves the width- relaxation when a partial homomorphism is fixed. This fixing of local solutions reduces the homomorphism or-construction to just solving equations over and , respectively, which the affine relaxation can do. To prove the second part of Theorem 3, we modify the homomorphism or-construction so that cohomology no longer solves it, but this also makes the template NP-complete.
2 Preliminaries
We write for . For and a set , let be the set of all subsets of of size at most . A relational vocabulary is a set of relation symbols with associated arities . A relational -structure is a tuple of a universe and interpretations of the relation symbols such that for all . We use letters , , and for finite relational structures. Their universes are denoted , , and , respectively. If is a structure and , then denotes the induced substructure with universe . For two -structures and , we write for the set of homomorphisms . A graph is a binary -structure, where we denote its vertex set by and its edge set by . Group operations are written as multiplication, for Abelian groups we use additive notation.
CSPs and Polymorphisms.
For a finite -structure , denote by the CSP with template , i.e., the class of finite -structures such that there is a homomorphism . We call a structure a -instance if has the same vocabulary as . The complexity of , and also the applicability of certain algorithms, is determined by the polymorphisms of the -structure . An -ary polymorphism is a map such that for every of arity and all , the tuple is also in (where denotes the -th entry of the tuple ). The polymorphisms of a structure are closed under composition. A ternary operation is Maltsev if it satisfies the identity for all inputs. For a group the map is a typical example of a Maltsev operation. The templates with Maltsev polymorphisms form a subclass of all tractable CSPs [12]. For more background on the algebraic approach to CSPs, see for example [5].
Logics, Interpretations, and Reductions.
A logic defines if there exists an -formula such that each instance satisfies if and only if . Inflationary fixed-point logic (IFP) is the extension of first-order logic by an operator defining inflationary fixed-points. IFP defines connected components of graphs, which is not possible in pure first-order logic. More details are not needed and we refer to [22, Chapter 8.1]. A logical interpretation is a (partial) map from -structures to -structures defined by logical formulas in the following way. For a -structure, a formula using vocabulary with free variables defines the set of all -tuples of the structure satisfying the formula. An interpretation consists of a formula defining the new universe, and for each relation symbol of a formula defining the relation in the new structure. Formal details are not needed in this paper, and for more details we refer to [22, Section 11.2] or the full version [28]. Such interpretations can be used as reductions between decision problems. Of particular interest in the context of CSPs are Datalog-interpretations, which can be expressed as IFP-interpretations (again see [22, Theorem 9.1.4]). Dalmau and Opršal [20] consider a variant of these reductions called Datalog∪-reductions. We omit a definition and only note that Datalog∪-reductions can be expressed as IFP-interpretations, too.
The -Consistency Algorithm.
A well-known heuristic for CSPs is the -consistency algorithm. For a template and an instance , the -consistency algorithm computes a map assigning to each a set of partial homomorphisms : it is the unique greatest fixed-point that satisfies the following properties for all .
- Forth-Condition:
-
Every extends to some , that is, .
- Down-Closure:
-
For every , we have .
If for some , then the algorithm rejects , otherwise it accepts.
CSP-Relaxation via Affine Systems of Linear Equations.
We introduce a system of linear equations due to Berkholz and Grohe [8], which will be used to (approximately) solve CSPs. We transfer hardness results for this system to other systems used in the different algorithms. Let be a template structure and be an instance. The width- affine relaxation aims to encode (approximately) whether is in .
Here is the unique homomorphism . If is at least the arity of , then if and only if has a nonnegative integral solution (and actually a -solution) [8]. We will be mainly interested in integral solutions of , so without the non-negativity restriction. To show the existence of these solutions, we will also consider special rational solutions:
Definition 4.
For , a -solution of a system of linear equations with variables is a solution of such that, for all , or for some .
Lemma 5 (restate=pqSolutionImpliesIntegral, name=[8]).
If and are coprime integers and a system of linear equations over has a -solution and a -solution, then has an integral solution, which is only non-zero for variables on which the -solution or the -solution is non-zero.
Group Coset-CSPs.
Let be a finite group. In a -coset-CSP [6, 23] variables range over and the constraints are of the following form. For an -tuple of variables , an -ary -coset-constraint is the constraint , where is a subgroup of and , that is, is a right coset of . With the term coset-CSP we refer to a -coset-CSP in this sense. For every finite group and every arity , there is a structure such that every -ary -coset-CSP is a -instance and contains all solvable -ary -coset-CSPs. is always tractable [23]. In fact, being a coset-CSP in this sense is equivalent to having the Maltsev polymorphism .
Lemma 6 (restate=groupCSPMaltsev, name=).
For every finite template and every binary operation such that is a group,
-
the map defined by is a polymorphism of if and only if
-
each relation is a coset of a subgroup of for some .
Thus, coset-CSPs are a natural class to study. In particular, being Maltsev, they are tractable even if is non-Abelian. By contrast, solving systems of equations is NP-complete if (and only if) is non-Abelian [25]. Systems of equations over an Abelian group can however always be viewed as a -coset-CSP. Hence, when we consider equation systems over Abelian groups in Section 4, we can treat them uniformly as coset-CSPs.
3 Homomorphism OR-Construction
For , let and be nonempty -structures and and be disjoint. The are templates and the the corresponding instances, and we assume that their universes are disjoint. We aim to define -structures and such that if and only if for some . Let be a fresh binary relation symbol and . The arities are inherited from and . The instance with universe has relations and for all and . We provide two variants of with different properties.
The Tractable Case.
The first variant of the template will preserve tractability of the and hence is called the tractable homomorphism or-construction. The template is defined as follows. Let and be two fresh vertices.
The construction is depicted in Figure 1. Intuitively, a homomorphism induces a homomorphism by mapping all vertices of to . The relation ensures that every homomorphism of is of this form, which proves the following lemma:
Lemma 7.
if and only if for some .
The next lemmas summarize the properties of the construction, which are required later: the tractable homomorpism or-construction preserves -consistency of the and inherits solutions of the width- affine relations from the .
Lemma 8 (restate = homOrTractableKConsistency, name = ).
Let , , , , , and . If and , then .
Lemma 9 (restate = homOrTractableSolution, name = ).
Let , , , and be a solution to . Then there exists a solution to defined, for all and all , by if and otherwise. In particular, is a -solution or integral, if is a -solution or integral, respectively.
Lemma 10 (restate = maltsevForOrConstruction, name = ).
If and have a Maltsev polymorphism, then has one.
Also if the are not Maltsev, tractability is preserved.
Lemma 11 (restate = homOrTractable, name = ).
If and are tractable, then is tractable.
For the proof of this lemma, we provide a polynomial-time algorithm for in [28]. Roughly speaking, the algorithm proceeds as follows: If the instance has more than one connected component, they can be treated individually. So we can assume that is connected. The algorithm divides the universe into two sets and such that elements in are contained in tuples of a -relation. If one is contained in both a - and a -relation, then is a no-instance. Because is connected, and are connected by the relation (not necessarily by a biclique). By the construction of the tractable or-construction, for any potential homomorphism there is an such that is mapped to and to . This can be tested by the algorithms for and . Note that this algorithm essentially only computes connected components and calls the decision algorithms of the . Hence, it can be expressed in logics that are at least expressive as IFP.
Corollary 12 (restate = homOrDefinable, name = ).
Let be a logic that is at least expressive as inflationary fixed-point logic. If and are -definable, then is -definable.
The tractable homomorphism or-construction has a drawback: forbidding a single partial homomorphism mapping vertices of to resolves the or-construction for the width- affine relaxation: every such solution to the width- affine relaxation of induces a solution for .
Lemma 13 (restate = integerSolutionWithLocalFixingSolvesBi, name = ).
Let , , and be a solution to . If there is a set such that for it holds that , then is a solution to .
In some situations this will cause problems later. To remedy this problem, we make the construction more flexible at the cost of giving up tractability.
The Intractable Case.
The second variant, which is called the intractable homomorphism or-construction, has the same universe as before, but interprets relations differently:
The construction is shown in Figure 1. The definition of still enforces that a homomorphism has to induce a homomorphism for one . Only for one , the extra vertex can be in the image of a homomorphism. Thus, this variant provides again a homomorphism-or construction, but now two partial homomorphisms and can be combined:
Lemma 14 (restate = homOrIntractableCompose, name = ).
Let , , for each , and consider homomorphisms for both . The map induced by and satisfies .
Also the intractable construction inherits solutions of the width- affine relaxation and preserves -consistency similar to Lemmas 8 and 9, but now for the combined partial homomorphisms. Instead of requiring that , we only require that . Already for easy templates the CSP of the intractable homomorphism-or construction is NP-complete. The reason is that for general instances the -relation does not have to be a biclique and hence a yes-instance does not have to induce a homomorphism for one at all. Even for choosing and to be the structure with a single element and one nonempty ternary relation, the intractable OR-construction yields an NP-complete CSP (e.g. shown by a reduction from -SAT). Many other CSPs can be reduced to this case, for example group-coset-CSPs.
4 Tseitin Formulas over Abelian Groups and Expanders
Our construction is based on graphs with high connectivity, so-called expanders. We do not give the standard definition of this notion because we only need one property of expanders, namely this: We say that a family of -connected -regular graphs is a family of expander graphs if there is a constant (the expansion constant) such that for all and , there is a set of size such that is empty or the edge set of a -connected subgraph of . The existence of such families is shown in [7, Corollary A.4]. Let be a -connected -regular graph. Fix an orientation of , i.e., a directed graph with one direction of each edge of . Let in this section. For a set , denote by the set of all such that . Analogously, is the set of all edges leaving , and . Fix a finite Abelian group . Let . Define the -coset-CSP , or for short, with variable set and linear equations
In the case , we obtain the classic Tseitin contradictions [32]. The CSP is solvable if and only if [8]. For all sets , the CSP implies the constraint defined via
Definition 15 (Robustly Consistent Assignments [8]).
For and a set , a partial assignment for is -consistent, if for every such that , the assignment satisfies the constraint . Note that is a partial solution if it is -consistent. We call robustly consistent if it is -consistent.
We review facts about robustly consistent assignments for . The detailed statements and proofs can be found in the full version and in [8]. The key idea is that the expansion property of ensures that is always locally satisfiable, on subinstances of size up to . This is because the inconsistency can be “shifted around” the graph to any equation outside of the local scope. Thus, for every set of at most variables, there is at least one robustly consistent assignment with domain . Robustly consistent assignments are also not discarded by the -consistency procedure. In particular, -consistency always accepts even if it has no solution.
Lemma 16 (consequence of [8, Lemma 4.6]).
If and is a -group (i.e., is a power of ), and , then there is a -solution of such that non-robustly consistent partial assignments are set to , and each robustly consistent partial solution is mapped to for some .
The above lemma can also be refined so that the resulting -solution assigns the value to for a single robustly consistent partial homomorphism of our choice.
5 Limitations of the Affine Algorithms
All of the affine algorithms are sound: they accept all yes-instances. This section shows that many of them are not complete on tractable CSPs: they do not reject all no-instances, and thus do not solve the CSP. We consider the tractable homomorphism or-construction of the ternary -coset-CSP and the ternary -coset-CSP.
5.1 -Affine -Consistency Relaxation
The -affine -consistency relaxation [20] solves the following system of affine linear equations over the integers. Let be a template, be an instance, and be a map assigning to every set a set of partial homomorphisms . Define the system :
For a fixed positive integer , a template structure , and an instance , the -affine -consistency relaxation runs the -consistency algorithm to compute , the function that maps each set to the set of -consistent partial homomorphisms . The instance is accepted by the algorithm if has an integral solution and rejects otherwise. Dalmau and Opršal [20] conjectured the following on the power of the -affine -consistency relaxation:
Conjecture 17 (restate=sthreeorZ, name = [20]).
For every finite structure , either is Datalog∪-reducible to or is Datalog∪-reducible to , where denotes the triangle.
Being Datalog∪-reducible to implies that is solved by -affine -consistency for some constant [20], which we show is not the case for our counterexample.
Theorem 18 (restate=zAffineDoesNotSolveBoundedColorClass, name =).
For every , the -affine -consistency relaxation does not solve . This is even true if is not a constant, but an at most sublinear function in the instance size.
Proof.
Let be a family of -regular -connected expander graphs and fix , for a large enough , such that is sufficiently larger than . Let be an orientation of . Let and . For , let , and be everywhere except at one vertex , where we set . For each , we consider the -ary -coset-CSP . Let and be the corresponding tractable homomorphism or-template. From it follows for both and thus by Lemma 7. For a set , a partial homomorphism is robustly consistent if is a robustly consistent partial homomorphism for some and , where is the fresh vertex of the or-construction. Robustly consistent partial solutions of the Tseitin systems are not discarded by -consistency, and by Lemma 8 this is also true for the robustly consistent partial homomorphisms of the or-instance. Then has a -solution for both by Lemma 16, which is only non-zero for variables indexed by robustly consistent partial homomorphisms. By Lemma 9, has a -solution in which only robustly consistent partial homomorphisms are non-zero, too. By Lemma 5, there is an integral solution to , which is only non-zero for robustly consistent partial solutions of . Such solutions to imply solutions to . Hence, the -affine -consistency relaxation wrongly accepts .
Lemma 19 (restate=notDatalogReducible, name =).
is not Datalog∪-reducible to .
Theorem 18 and Lemma 19 disprove Conjecture 17. To show the lemma, we show that is not Datalog∪-reducible to for a prime . This suffices because is Datalog∪-reducible to [20]. We use results from finite model theory: -rank logic [21] extends IFP by a rank operator for definable matrices over and . The logic defines and and so also by Corollary 12. If is Datalog∪-reducible to , then -rank logic solves because IFP expresses Datalog∪-reductions. But -equation systems are only solvable in -rank logic if [26].
5.2 BLP+AIP and BAk
We introduce another well-studied system of equations for CSPs [3, 10] parameterized by the size of partial solutions [15]. Let be a positive integer, a template -structure and a -instance. We define the system with variable set .
Different domains of the variables (see [10]) are of interest: If we restrict the variables to , then is solvable if and only if . The relaxation of to nonnegative rationals is the -basic linear programming (BLP) relaxation 111The literature [10, 16] only calls the basic linear programming relaxation. For convenience and uniformity, we extend the notion in this paper to arbitrary .. The affine relaxation of to all integers is the -affine integer programming (AIP) relaxation . By increasing the parameter , the BLP and AIP relaxations result in the Sherali-Adams LP hierarchy [30] and the affine integer programming hierarchy [15] of the -system, respectively. In contrast to the -affine -consistency relaxation, the BLP+AIP algorithm is not parameterized by the size of partial solutions . Ciardo and Živný [18, 16] proposed this parameterized version called BAk, where BA1 is just the BLP+AIP algorithm.
The original presentation of BAk [18] uses a slightly different system of equations but one can easily verify that our presentation is equisatisfiable. The system in [18] does not have variables but uses variables instead, where is the full -ary relation. We deviate from the presentation in [18] to keep it consistent with the systems for the other algorithms. We show that BAk fails on the counterexample provided for -affine -consistency.
Theorem 20 (restate=BLPDoesNotSolveBoundedColorClass, name=).
For every integer , the algorithm does not solve . This is even true if is not a constant but an at most sublinear function in the instance size.
The theorem is proved using the same construction as for Theorem 18. One shows, for at least the arity of , that a non-negative or integral solution of implies a solution for or , respectively. The solution to , where is the Tseitin-system over , is non-zero and non-negative exactly for the robustly consistent partial homomorphisms. This carries over to the notion of robustly consistent partial homomorphisms for the or-instance . This implies that the interior point computed in Step 1 is non-zero for robustly consistent partial homomorphisms. So they are not set to zero in Step 2 and there is an integral solution.
5.3 The CLAP Algorithm
The CLAP algorithm [17] combines the BLP and the AIP relaxation. It first iteratively reduces the solution space using BLP by fixing partial solutions to and discarding those for which this refined BLP is not solvable. Then BLP+AIP is run on the restricted solution space, where again a partial solution is fixed:
Note that the algorithm accepts in Step 4 if for one , one , and one BLP+AIP accepts when fixing the partial solution (in contrast to the stronger requirement that for each and , there is one for which BLP+AIP accepts). We show that this weaker requirement can actually by omitted and does not change whether CLAP solves . This is crucial to show that CLAP fails on the same counterexample.
Theorem 21 (restate=clapDoesNotSolveAll, name = ).
does not solve .
We prove this theorem again with the construction from the proof of Theorem 18, where we pick to be the arity of . Again we have to argue that the pruning steps never remove robustly consistent partial homomorphisms. Here we also need the property of the Tseitin systems that their relaxation admits a -solution even if we require a given partial homomorphism to receive value . Theorems 18, 20, and 21 prove Theorem 1. Our arguments do not exploit that CLAP uses and and is not parametrized by a width . Hence, a parameterized version of CLAP will fail on the same counterexample.
5.4 The Cohomological -Consistency Algorithm
The cohomological -consistency algorithm due to Ó Conghaile [19] was originally presented in categorical and cohomological notions but computing cohomology groups is nothing else than solving a system of linear equations over the integers. Therefore, we can state the algorithm in a way similar to the other algorithms seen so far.
Step 2b of the algorithm approximates whether there is a global homomorphism whose restriction to is equal to via solving the in which we set and for all other . At least for the template , the cohomological -consistency algorithm is strictly more powerful than the previous ones because it correctly rejects the instances:
Theorem 22 (restate=cohomologySolvesCounterexample, name=).
If are templates of Abelian coset-CSPs and for both , then the cohomological -consistency algorithm solves .
The proof exploits Lemma 13: When a partial homomorphism of is fixed as in Step 2(b) of the algorithm, then the tractable homomorphism or-construction is resolved: (with the additional constraints) has an integral solution only if has an integral solution. But for Abelian coset-CSPs, has an integral solution if and only if (see Section 6). This means that there is no integral solution and the algorithm rejects . Actually, showing that the cohomological algorithm correctly solves all instances also follows the algorithm for Lemma 11. While the algorithm correctly solves the tractable homomorphism or-construction, it fails on the intractable one. This proves without complexity-theoretic assumptions like P NP that this polynomial-time algorithm does not solve all finite-domain CSPs.
Theorem 23 (restate=cohomologyDoesNotSolveAllCSP, name =).
There is an NP-complete template structure such that for every constant , the cohomological -consistency algorithm does not solve .
The theorem is proved using the same setup as in the counterexample for the other algorithms, but we use the intractable homomorphism or-construction. This makes the crucial difference that, by Lemma 14, two partial homomorphisms of both and can be combined into a partial homomorphism . If both partial homomorphisms are robustly consistent, then also their combination is not ruled out by -consistency. When a partial solution is fixed in Step 2, there is still a -solution for both . Hence there is an integral solution by Lemma 5. Thus, all robustly consistent assignments survive Step 2. As indicated in Section 3, is NP-complete. Theorems 22 and 23 prove Theorem 3.
6 Affine Algorithms and Coset-CSPs
The counterexample we have used so far is not a coset-CSP itself, but a combination of two Abelian coset-CSPs in the homomorphism or-construction. We now set out to explore the power of the affine algorithms on coset-CSPs. It follows from [3] that solving for (often just called AIP) suffices to solve all Abelian coset-CSPs. Since all algorithms considered are at least as powerful as AIP, this proves Theorem 2 (1). But there are non-Abelian groups for which AIP still works: These are 2-nilpotent groups of odd order, for example certain non-Abelian semidirect products for each odd prime . For these groups, the Maltsev operation for a certain Abelian group is a polymorphism of the non-Abelian template. It follows again from [3] that AIP solves the -coset-CSP. We thank Michael Kompatscher for this proof idea. This proves Theorem 2 (3).
It remains to show Theorem 2 (2), i.e., that the affine algorithms studied in Section 5 also fail on coset-CSPs. The key idea is to translate our counterexample from Section 5 into a coset-CSP such that hardness for the algorithms is preserved. This is achieved via a series of reduction steps: We start again with Tseitin systems and over and , respectively.
These systems, like every coset-CSP, can be reduced, by a variant of the well-known CFI construction [13], to the graph isomorphism problem for graphs of bounded color class size [8]. These are vertex-colored graphs in which only a constant number of vertices have the same color. The reduction gives for each two colored graphs and that are isomorphic if and only if . Next, we use an isomorphism or-construction, similar to the one in [8]. This yields two colored graphs which are isomorphic if and only if for at least one we have . Finally, this isomorphism problem is expressed as a binary -coset-CSP [8], where is the size of the color classes, which is in our case. This -coset CSP has a solution if and only if at least one of the initial two Tseitin instances has a solution – which by construction is not the case.
The technical difficulty is showing that the hardness of the instances is preserved via the reduction steps. One can indeed show that the translations from group-coset-CSPs to bounded color class size graph isomorphism and back as well as the isomorphism or-construction preserve solutions of the width- affine relaxation and -consistency in a similar way as we did this for the homomorphism or-construction in Section 3. In the end, we are essentially in the same setting as in the proofs in Section 5. We find a suitable notion of robustly consistent partial homomorphisms which are not ruled out by -consistency. We also get -solutions to the width- affine relaxation of the -coset-CSP, which are only non-zero for robustly consistent partial homomorphisms. Thus, using Lemma 5, we obtain an integral solution. By following the same reasoning as in Section 5, we can show that neither the -affine -consistency relaxation, BAk, nor CLAP solve . We provide a full proof including a description of the reduction steps in the full version.
7 Conclusion
Regarding the question for a universal polynomial-time CSP algorithm, we conclude that most of the affine algorithms from recent years are not powerful enough. Only cohomological -consistency remains as a candidate because it sets local solutions to when solving the affine relaxation. We are aware of another algorithm with this feature: This is C(BLP+AIP), a variation of CLAP mentioned in [17] and defined more explicitly in [14]. This algorithm also involves solving the integer relaxation where additionally a local solution is set to . We expect that it solves our counterexample, too. In [14], it is shown that C(BLP+AIP) fails on certain intractable templates but it remains an intriguing open question to find a tractable counterexample for C(BLP+AIP) and cohomological -consistency. Another question that we have not addressed is the relationship between the different algorithms. It is obvious from the definitions that cohomological -consistency subsumes -affine -consistency, and that CLAP subsumes BLP+AIP. How the -consistency based methods compare to the BLP-based ones remains unanswered; it may be that they are incomparable. In particular, we would like to know if cohomological -consistency strictly subsumes all the other algorithms. In light of our results, this seems likely, but since the cohomological algorithm does not use the BLP, it is not obvious how it compares to, say, BAk.
References
- [1] Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau. On the power of k-consistency. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 279–290. Springer, 2007. doi:10.1007/978-3-540-73420-8_26.
- [2] Libor Barto. The collapse of the bounded width hierarchy. Journal of Logic and Computation, 26(3):923–943, November 2014. doi:10.1093/logcom/exu070.
- [3] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1–28:66, 2021. doi:10.1145/3457606.
- [4] Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In 2009 50th Annual IEEE symposium on foundations of computer science, pages 595–603. IEEE, 2009. doi:10.1109/FOCS.2009.32.
- [5] Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017. doi:10.4230/DFU.Vol7.15301.1.
- [6] Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 155–166. Springer, 2015. doi:10.1007/978-3-662-47672-7_13.
- [7] Christoph Berkholz and Martin Grohe. Linear Diophantine equations, group CSPs, and graph isomorphism. CoRR, abs/1607.04287, 2016. arXiv:1607.04287.
- [8] Christoph Berkholz and Martin Grohe. Linear Diophantine equations, group CSPs, and graph isomorphism. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 327–339. SIAM, 2017. doi:10.1137/1.9781611974782.21.
- [9] Joshua Brakensiek and Venkatesan Guruswami. An algorithmic blend of LPs and ring equations for promise CSPs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 436–455. SIAM, 2019. doi:10.1137/1.9781611975482.28.
- [10] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. The power of the combined basic LP and affine relaxation for promise CSPs. Electron. Colloquium Comput. Complex., TR20-004, 2020. URL: https://eccc.weizmann.ac.il/report/2020/004.
- [11] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330, 2017. doi:10.1109/FOCS.2017.37.
- [12] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal’tsev constraints. SIAM J. Comput., 36(1):16–27, 2006. doi:10.1137/050628957.
- [13] Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992. doi:10.1007/BF01305232.
- [14] Siu On Chan and Hiu Tsun Ng. How random CSPs fool hierarchies: II. Electron. Colloquium Comput. Complex., TR25-026, 2025. To appear at STOC 2025. URL: https://eccc.weizmann.ac.il/report/2025/026.
- [15] Lorenzo Ciardo and Stanislav Živný. Approximate graph colouring and crystals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2256–2267. SIAM, 2023. doi:10.1137/1.9781611977554.CH86.
- [16] Lorenzo Ciardo and Stanislav Živný. Approximate graph colouring and the hollow shadow. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 623–631. ACM, 2023. doi:10.1145/3564246.3585112.
- [17] Lorenzo Ciardo and Stanislav Živný. CLAP: A new algorithm for promise CSPs. SIAM J. Comput., 52(1):1–37, 2023. doi:10.1137/22M1476435.
- [18] Lorenzo Ciardo and Stanislav Živný. Hierarchies of minion tests for PCSPs through tensors. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 568–580. SIAM, 2023. doi:10.1137/1.9781611977554.CH25.
- [19] Adam Ó Conghaile. Cohomology in constraint satisfaction and structure isomorphism. In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, volume 241 of LIPIcs, pages 75:1–75:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.MFCS.2022.75.
- [20] Víctor Dalmau and Jakub Opršal. Local consistency as a reduction between constraint satisfaction problems. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024, pages 29:1–29:15. ACM, 2024. doi:10.1145/3661814.3662068.
- [21] Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner. Logics with rank operators. In 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, pages 113–122. IEEE Computer Society, 2009. doi:10.1109/LICS.2009.24.
- [22] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite model theory. Perspectives in Mathematical Logic. Springer, Berlin, Heidelberg, 1995. doi:10.1007/978-3-662-03182-7.
- [23] Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 612–622, 1993. doi:10.1145/167088.167245.
- [24] Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36–41. IEEE Computer Society, 1980. doi:10.1109/SFCS.1980.34.
- [25] Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Information and Computation, 178(1):253–262, 2002. doi:10.1006/inco.2002.3173.
- [26] Erich Grädel and Wied Pakusa. Rank logic is dead, long live rank logic! J. Symb. Log., 84(1):54–87, 2019. doi:10.1017/jsl.2018.33.
- [27] Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499–507, 1979. doi:10.1137/0208040.
- [28] Moritz Lichter and Benedikt Pago. Limitations of affine integer relaxations for solving constraint satisfaction problems, 2025. doi:10.48550/arXiv.2407.09097.
- [29] Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1986.
- [30] Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3(3):411–430, 1990. doi:10.1137/0403036.
- [31] Johan Thapper and Stanislav Živný. The complexity of finite-valued CSPs. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 695–704, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488697.
- [32] Grigori Samuilovitsch Tseitin. On the Complexity of Derivation in Propositional Calculus, pages 466–483. Springer Berlin Heidelberg, Berlin, Heidelberg, 1983. doi:10.1007/978-3-642-81955-1_28.
- [33] Dmitriy Zhuk. The proof of CSP dichotomy conjecture. Journal of the ACM, 67, April 2017. doi:10.1145/3402029.