pith. sign in

arxiv: 2602.14243 · v2 · submitted 2026-02-15 · 💻 cs.CC · cs.DM· math.LO· math.RA

Graph Homomorphisms and Universal Algebra

Manuel Bodirsky This is my paper

Pith reviewed 2026-05-15 21:55 UTC · model grok-4.3

classification 💻 cs.CC cs.DMmath.LOmath.RA
keywords constraint satisfaction problemsuniversal algebragraph homomorphismscyclic termsbounded widthpolymorphismscomputational complexityNP-hardness
0
0 comments X

The pith

Cyclic terms and bounded width theorems classify exactly which finite-domain constraint satisfaction problems are polynomial-time tractable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops the universal-algebraic approach to constraint satisfaction by beginning with concrete graph homomorphism problems and building to algebraic invariants of the template. It shows that tractability holds precisely when the polymorphism algebra admits a cyclic term or satisfies the bounded-width condition. A sympathetic reader cares because these criteria give a uniform, checkable way to decide whether a given CSP instance can be solved efficiently or must be NP-hard. The development therefore turns an apparently scattered collection of easy and hard problems into a single classification theorem.

Core claim

Finite-domain CSPs are in P if and only if their polymorphism clone contains a cyclic term or the instance has bounded width; otherwise the problem is NP-complete. The course proves both directions by reducing the algebraic conditions to known tractable algorithms (such as arc consistency or Datalog) and constructing hardness reductions when neither condition holds.

What carries the argument

A cyclic term is a polymorphism that satisfies a cyclic identity; bounded width is the property that the template admits a certain Datalog program of bounded treewidth. Together they serve as the decision criteria that separate tractable templates from NP-hard ones.

If this is right

  • Any CSP whose template has a cyclic polymorphism can be solved by a local consistency procedure.
  • Bounded-width templates admit a Datalog formulation that decides satisfiability in linear time.
  • Absence of both cyclic terms and bounded width yields a polynomial-time reduction from 3-coloring or another NP-complete problem.
  • The same algebraic conditions decide the complexity of the homomorphism problem for any finite directed graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The classification immediately supplies an algorithm that, given the template, outputs either a polynomial-time procedure or a proof of NP-hardness.
  • The same invariants may guide the search for tractable restrictions when the domain is allowed to grow with the input size.
  • Graph homomorphism problems become the base case from which the entire theory is built, so every later theorem is a direct lift of a graph-theoretic fact.

Load-bearing premise

The template of the CSP is a finite relational structure whose polymorphisms can be analyzed algebraically.

What would settle it

Exhibit a concrete finite template whose CSP is solvable in polynomial time yet whose polymorphism clone contains neither a cyclic term nor admits bounded width.

Figures

Figures reproduced from arXiv: 2602.14243 by Manuel Bodirsky.

Figure 1
Figure 1. Figure 1: Illustration of the uniqueness proof for cores [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The arc-consistency procedure for CSP(H). • remove u from L(x) if there is no v ∈ L(y) with (u, v) ∈ E(H); • remove v from L(y) if there is no u ∈ L(x) with (u, v) ∈ E(H). If eventually we cannot remove any vertex from any list with these rules any more, the digraph G together with the lists for each vertex is called arc-consistent. The pseudo-code of the entire arc-consistency procedure is displayed in [… view at source ↗
Figure 3
Figure 3. Figure 3: The AC-3 implementation of the arc-consistency procedure for CSP( [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The graph from Exercise 49. 47. Solve the problems from the previous exercise for infinite digraphs H. 48. Up to isomorphism, there is only one unbalanced cycle H on four vertices that is a core and not the directed cycle. Show that AC does not solve CSP(H). 49. Can the CSP for the digraph depicted in [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: One of the smallest orientations of a tree [PITH_FULL_IMAGE:figures/full_fig_p030_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The (strong) path-consistency procedure for CSP( [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The graph C ++ 2 from Exercise 78. 4.3 Testing for Majority Polymorphisms In this section we show that the question whether a given digraph has a majority polymor￾phism can be decided in polynomial time. The method that we present is sometimes referred to as a self-reduction and can be adapted for several other polymorphism conditions and several other algorithms (see Exercise 168). Majority-Test(H) Input:… view at source ↗
Figure 8
Figure 8. Figure 8: A polynomial-time algorithm to find majority polymorphisms. [PITH_FULL_IMAGE:figures/full_fig_p036_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: A totally rectangular digraph. Theorem 4.13 (Kazda [71]). If a finite digraph H has a Maltsev polymorphism then H also has a majority polymorphism. Hence, for finite digraphs H with a Maltsev polymorphism, the strong path-consistency procedure solves the H-colouring problem, and in fact even the precoloured H-colouring problem. Theorem 4.13 is an immediate consequence of Theorem 4.19 below; to state it, we… view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of E(K3) ≤ A2 , where Clo(A) = Pol(K3), as a bipartite graph. 141. Consider the algebra An := ({0, . . . , n − 1}; m) where m(x, y, z) := x − y + z. Then for every k ≥ 1 the clone Clo(An) (k) consists of precisely the operations defined as g(x0, . . . , xk−1) := X i aixi where a0, . . . , ak−1 ∈ Z with P i ai = 1. 142. Let p be a positive prime. Show that the only proper subalgebras of Ap fro… view at source ↗
Figure 11
Figure 11. Figure 11: Define µ: S → A by µ(t Bm (c1, . . . , ck)) := t A(a1, . . . , ak). Claim 1: µ is well-defined. Suppose that t Bm (c1, . . . , ck) = s Bm (c1, . . . , ck); then t B = s B by the choice of S, and by assumption we have t A(a1, . . . , ak) = s A(a1, . . . , ak). 84 [PITH_FULL_IMAGE:figures/full_fig_p084_11.png] view at source ↗
Figure 11
Figure 11. Figure 11: Illustration for the proof of Birkhoff’s theorem [PITH_FULL_IMAGE:figures/full_fig_p085_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The procedure Nonempty. 8.4 The Bulatov-Dalmau Algorithm Let ∃x1, . . . , xn(ϕ1 ∧ · · · ∧ ϕm) be an instance of CSP(A). For ℓ ≤ m, we write Rℓ for the relation {(s1, . . . , sn) ∈ A n | A |= (ϕ1 ∧ · · · ∧ ϕℓ)(s1, . . . , sn)}. The idea of the algorithm is to inductively construct a compact representation R′ ℓ of Rℓ , adding constraints one by one. Initially, for ℓ = 0, we have Rℓ = An , and it is easy to … view at source ↗
Figure 13
Figure 13. Figure 13: The procedure Fix-values. Running time. The number of iterations of the while loop can be bounded by the size |U| of the set U at the end of the execution of the procedure. Hence, when we want to use this procedure to obtain a polynomial-time running time, we have to make sure that the size of U remains polynomial in the input size. The way this is done in the Bulatov-Dalmau algorithm is to guarantee that… view at source ↗
Figure 14
Figure 14. Figure 14: The procedure Next. • the condition Nonempty(Fix-values(R′ , t1, . . . , ti−1), i1, . . . , ik, i, S × {b}) ̸= ‘No’ from the second if-clause is satisfied if and only if there exists a tuple t ′ ∈ R such that – (t ′ 1 , . . . , t′ i−1 ) = (t1, . . . , ti−1), – (t ′ i1 , . . . , t′ ik ) ∈ S, and – t ′ i = b. If this condition holds, and since ti = a, we have that t and t ′ witness (i, a, b). It only remain… view at source ↗
Figure 15
Figure 15. Figure 15: A dictionary between corresponding notions. [PITH_FULL_IMAGE:figures/full_fig_p109_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Diagram for the proof of Lemma 10.2. We claim that the graph B/T (see Example 5.13) does not contain loops. It suffices to show that T ∩ E = ∅. Otherwise, let (a, b) ∈ T ∩ E. Choose (a, b) in such a way that the shortest sequence a = a0, a1, . . . , an = b with R(a0, a1), R(a1, a2), . . . , R(an−1, an) in B is shortest possible; see [PITH_FULL_IMAGE:figures/full_fig_p117_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Diagram for the proof of Lemma 10.3. • The tuple (r, zk) := (r1, . . . , rk−1, zk) is a common neighbour of both x and (s, xk). • Finally, for i ̸= k choose ti to be distinct from zi and ri , and choose tk to be distinct from zk and from z ′ k . Then t := (t1, . . . , tk−1, tk) is a common neighbour of (z, zk), of (z, z′ k ), and of (r, zk). The situation is illustrated in [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 18
Figure 18. Figure 18: Illustrations of R ≤ A × B with non-empty left center C (left side), and of R ≤ A × B which is linked (right side); none of the two examples is subdirect. is transitive, because for every a ∈ A and j ∈ {1, . . . , |A|} |t ∗ · · · ∗ t | {z } j times (A, . . . , A, {a} |{z} i , A, . . . , A)| ≥ j and hence u(A, . . . , A, {a} |{z} i , A, . . . , A) = A. Corollary 13.27. Let A be a finite idempotent Taylor a… view at source ↗
Figure 19
Figure 19. Figure 19: An illustration for the definition of SE in the proof Proposition 13.32. • SB = ∅ because the left centre of R is empty. Let D be maximal such that SD = B2 , and let E ⊆ B and b ∈ B be a set such that E \ D = {b}. See [PITH_FULL_IMAGE:figures/full_fig_p143_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: An illustration for the definition of central absorption (Definition 13.42). [PITH_FULL_IMAGE:figures/full_fig_p148_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: Diagram for the proof of Lemma 14.3. such that f A(a) = f A(ρ(a)) = · · · = f A(ρ k−1 (a)). Choose f such that |S(f)| is maximal (here we use the assumption that A is finite). If |S(f)| = |Ak |, then f A is cyclic and we are done. Otherwise, arbitrarily pick a = (a0, a1, . . . , ak−1) ∈ Ak \ S(f). For i ∈ {0, . . . , k − 1}, define bi := f(ρ i (a)), and let B := {b, ρ(b), . . . , ρk−1 (b)}. We claim that … view at source ↗
Figure 22
Figure 22. Figure 22: The smooth digraph leading to the Siggers terms of arity four. [PITH_FULL_IMAGE:figures/full_fig_p170_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: The singleton arc-consistency procedure for CSP( [PITH_FULL_IMAGE:figures/full_fig_p175_23.png] view at source ↗
read the original abstract

Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational complexity, and in particular the border between polynomial-time tractability and NP-hardness. In this course we introduce the universal-algebraic approach to study the computational complexity of finite-domain CSPs. The course covers in particular the cyclic terms and bounded width theorems. To keep the presentation accessible, we start the course in the tangible setting of directed graphs and graph homomorphism problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript consists of course notes introducing the universal-algebraic approach to the computational complexity of finite-domain constraint satisfaction problems (CSPs). Beginning with directed graphs and graph homomorphism problems as a concrete entry point, it surveys the cyclic terms theorem and the bounded width theorem, which characterize the polynomial-time tractable cases.

Significance. If the exposition accurately reflects the established theorems, the notes provide a valuable pedagogical resource for bridging graph theory and universal algebra in the study of CSP complexity. The choice to start from tangible homomorphism problems lowers the entry barrier for readers with standard graph-theoretic background, and the focus on the cyclic terms and bounded-width results highlights two central pillars of the algebraic dichotomy theory. The work contains no new derivations but offers a structured survey of known results.

minor comments (2)
  1. Add explicit citations to the original sources of the cyclic terms theorem and bounded width theorem (e.g., Barto-Kozik and related works) at the points where the statements are introduced, to allow readers to locate the full proofs.
  2. Consider including a short concluding section that summarizes the main algebraic invariants and their algorithmic consequences, to reinforce the connection between the graph-homomorphism examples and the general CSP tractability results.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our course notes and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity: survey of established theorems only

full rationale

The document is course notes surveying known results (cyclic terms theorem, bounded-width theorem) on algebraic CSP complexity. It introduces graph homomorphisms pedagogically but advances no new derivations, equations, or claims. All load-bearing statements are explicitly attributed to prior literature without reduction to self-citations, fitted inputs, or self-definitional constructs inside the paper. The presentation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The presentation relies on standard background results in universal algebra and graph theory rather than introducing new free parameters or entities.

axioms (1)
  • standard math Basic properties of graph homomorphisms and the correspondence between CSPs and algebras
    Invoked at the outset to move from concrete graphs to algebraic terms.

pith-pipeline@v0.9.0 · 5367 in / 1042 out tokens · 17182 ms · 2026-05-15T21:55:19.279376+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

112 extracted references · 112 canonical work pages · 2 internal anchors

  1. [1]

    Aaronson

    S. Aaronson. P= ?NP.Electronic Colloquium on Computational Complexity (ECCC), 24:4, 2017

    work page 2017

  2. [2]

    Ahlbrandt and M

    G. Ahlbrandt and M. Ziegler. Quasi-finitely axiomatizable totally categorical theories. Annals of Pure and Applied Logic, 30(1):63–82, 1986

    work page 1986

  3. [3]

    Aichinger, P

    E. Aichinger, P. Mayr, and R. McKenzie. On the number of finite algebraic structures. Journal of the European Mathematical Society, 16(8):1673–1686, 2014

    work page 2014

  4. [4]

    Aspvall, M

    B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas.Information Processing Letters, 8(3):121–123, 1979

    work page 1979

  5. [5]

    Atserias, A

    A. Atserias, A. A. Bulatov, and A. Dawar. Affine systems of equations and counting infinitary logic.Theoretical Computer Science, 410(18):1666–1683, 2009. 199

    work page 2009

  6. [6]

    L. Barto. The dichotomy for conservative constraint satisfaction problems revisited. In Proceedings of the Symposium on Logic in Computer Science (LICS), Toronto, Canada, 2011

    work page 2011

  7. [7]

    L. Barto. Finitely related algebras in congruence distributive varieties have near una- nimity terms.Canadian Journal of Mathematics, 65(1):3–21, 2013

    work page 2013

  8. [8]

    Barto, Z

    L. Barto, Z. Brady, A. Bulatov, M. Kozik, and D. Zhuk. Unifying the three algebraic approaches to the csp via minimal taylor algebras.TheoretiCS, Volume 3, May 2024

    work page 2024

  9. [9]

    Barto, J

    L. Barto, J. Bul´ ın, A. A. Krokhin, and J. Oprˇ sal. Algebraic approach to promise constraint satisfaction.J. ACM, 68(4):28:1–28:66, 2021

    work page 2021

  10. [10]

    Barto and A

    L. Barto and A. Kazda. Deciding absorption.Int. J. Algebra Comput., 26(5):1033–1060, 2016

    work page 2016

  11. [11]

    Barto and M

    L. Barto and M. Kozik. Constraint satisfaction problems of bounded width. InPro- ceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 595–603, 2009

    work page 2009

  12. [12]

    Barto and M

    L. Barto and M. Kozik. Absorbing subalgebras, cyclic terms and the constraint satis- faction problem.Logical Methods in Computer Science, 8/1(07):1–26, 2012

    work page 2012

  13. [13]

    Barto and M

    L. Barto and M. Kozik. Absorption in universal algebra and CSP. InThe Constraint Satisfaction Problem: Complexity and Approximability, volume 7 ofDagstuhl Follow- Ups, pages 45–77, 2017

    work page 2017

  14. [14]

    Barto, M

    L. Barto, M. Kozik, and T. Niven. The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell).SIAM Journal on Computing, 38(5), 2009

    work page 2009

  15. [15]

    Barto, M

    L. Barto, M. Kozik, and D. Stanovsk´ y. Mal’tsev conditions, lack of absorption, and solvability.Algebra Universalis, 74:185–206, 2015

    work page 2015

  16. [16]

    Barto, A

    L. Barto, A. A. Krokhin, and R. Willard. Polymorphisms, and how to use them. InThe Constraint Satisfaction Problem: Complexity and Approximability, pages 1–44. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017

    work page 2017

  17. [17]

    Barto, J

    L. Barto, J. Oprˇ sal, and M. Pinsker. The wonderland of reflections.Israel Journal of Mathematics, 223(1):363–398, 2018

    work page 2018

  18. [18]

    N. Biggs. Constructions for cubic graphs with large girth.Electronic Journal of Com- binatorics, 5, 1998

    work page 1998

  19. [19]

    Birkhoff

    G. Birkhoff. On the structure of abstract algebras.Mathematical Proceedings of the Cambridge Philosophical Society, 31(4):433–454, 1935

    work page 1935

  20. [20]

    Blass, Y

    A. Blass, Y. Gurevich, and S. Shelah. Choiceless polynomial time.Annals of Pure and Applied Logic, 100(1-3):141–187, 1999

    work page 1999

  21. [21]

    Bodirsky.Complexity of Infinite-Domain Constraint Satisfaction

    M. Bodirsky.Complexity of Infinite-Domain Constraint Satisfaction. Lecture Notes in Logic (52). Cambridge University Press, Cambridge, United Kingdom; New York, NY, 2021. 200

    work page 2021

  22. [22]

    Bodirsky

    M. Bodirsky. Model theory, 2022. Course Notes, TU Dresden,https://wwwpub.zih. tu-dresden.de/~bodirsky/Model-theory.pdf

    work page 2022

  23. [23]

    Bodirsky

    M. Bodirsky. Diskrete Strukturen, 2023. Skript zur Vorlesung, TU Dresden,https: //wwwpub.zih.tu-dresden.de/~bodirsky/Diskrete-Strukturen.pdf

    work page 2023

  24. [24]

    Bodirsky

    M. Bodirsky. Introduction to mathematical logic, 2023. Course notes, TU Dresden, https://wwwpub.zih.tu-dresden.de/~bodirsky/Logic.pdf

    work page 2023

  25. [25]

    Bodirsky, J

    M. Bodirsky, J. Bul´ ın, F. Starke, and M. Wernthaler. The smallest hard trees.Con- straints, abs/2205.07528, 2022

    work page arXiv 2022

  26. [26]

    Bodirsky and J

    M. Bodirsky and J. Neˇ setˇ ril. Constraint satisfaction with countable homogeneous tem- plates.Journal of Logic and Computation, 16(3):359–373, 2006

    work page 2006

  27. [27]

    Bodirsky and M

    M. Bodirsky and M. Pinsker. Topological Birkhoff.Transactions of the American Mathematical Society, 367(4):2527–2549, 2015

    work page 2015

  28. [28]

    Bodirsky and F

    M. Bodirsky and F. Starke. Maximal digraphs with respect to primitive positive con- structability.Combinatorica, 42:997–1010, 2022

    work page 2022

  29. [29]

    Bodirsky, F

    M. Bodirsky, F. Starke, and A. Vucaj. Smooth digraphs modulo primitive positive constructability and cyclic loop conditions.International Journal on Algebra and Com- putation, 31(5):939–967, 2021. Preprint available at ArXiv:1906.05699

    work page arXiv 2021

  30. [30]

    Bodirsky and A

    M. Bodirsky and A. Vucaj. Two-element structures modulo primitive positive con- structability.Algebra Universalis, 81(20), 2020. Preprint available at ArXiv:1905.12333

    work page arXiv 2020

  31. [31]

    Bodirsky, A

    M. Bodirsky, A. Vucaj, and D. Zhuk. The lattice of clones of self-dual operations collapsed.International Journal on Algebra and Computation, 2023. Preprint available at https://arxiv.org/abs/2109.01371

    work page arXiv 2023

  32. [32]

    V. G. Bodnarˇ cuk, L. A. Kaluˇ znin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras, part I and II.Cybernetics, 5:243–539, 1969

    work page 1969

  33. [33]

    Brakensiek and V

    J. Brakensiek and V. Guruswami. Promise constraint satisfaction: Algebraic structure and a symmetric boolean dichotomy.SIAM J. Comput., 50(6):1663–1700, 2021

    work page 2021

  34. [34]

    A. A. Bulatov. Tractable conservative constraint satisfaction problems. InProceedings of the Symposium on Logic in Computer Science (LICS), pages 321–330, Ottawa, Canada, 2003

    work page 2003

  35. [35]

    A. A. Bulatov. H-coloring dichotomy revisited.Theoretical Computer Science, 349(1):31–39, 2005

    work page 2005

  36. [36]

    A. A. Bulatov. Conservative constraint satisfaction re-revisited.Journal Computer and System Sciences, 82(2):347–356, 2016. ArXiv:1408.3690

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  37. [37]

    A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 319–330, 2017. 201

    work page 2017

  38. [38]

    A. A. Bulatov and V. Dalmau. A simple algorithm for Mal’tsev constraints.SIAM Journal on Computing, 36(1):16–27, 2006

    work page 2006

  39. [39]

    A. A. Bulatov and P. Jeavons. Algebraic structures in combinatorial problems. Technical report MATH-AL-4-2001, Technische Universit¨ at Dresden, 2001

    work page 2001

  40. [40]

    A. A. Bulatov, A. A. Krokhin, and P. G. Jeavons. Classifying the complexity of con- straints using finite algebras.SIAM Journal on Computing, 34(3):720–742, 2005

    work page 2005

  41. [41]

    J. Bul´ ın. On the complexity ofH-coloring for special oriented trees.Eur. J. Comb., 69:54–75, 2018

    work page 2018

  42. [42]

    Bul´ ın, D

    J. Bul´ ın, D. Delic, M. Jackson, and T. Niven. A finer reduction of constraint problems to digraphs.Log. Methods Comput. Sci., 11(4), 2015

    work page 2015

  43. [43]

    S. N. Burris and H. P. Sankappanavar.A Course in Universal Algebra. Springer Verlag, Berlin, 1981

    work page 1981

  44. [44]

    Carvalho, L

    C. Carvalho, L. Egri, M. Jackson, and T. Niven. On Maltsev digraphs.Electr. J. Comb., 22(1):P1.47, 2015

    work page 2015

  45. [45]

    H. Chen, V. Dalmau, and B. Grußien. Arc consistency and friends.J. Log. Comput., 23(1):87–108, 2013

    work page 2013

  46. [46]

    Chen and B

    H. Chen and B. Larose. Asking the metaquestions in constraint tractability.TOCT, 9(3):11:1–11:27, 2017

    work page 2017

  47. [47]

    D. A. Cohen, M. C. Cooper, P. G. Jeavons, and S.ˇZivn´ y. Binarisation via dualisation for valued constraints. InProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 3731–3737, 2015

    work page 2015

  48. [48]

    Cs´ ak´ any

    B. Cs´ ak´ any. Minimal clones.Algebra Universalis, 54(1):73–89, 2005

    work page 2005

  49. [49]

    V. Dalmau. Linear Datalog and bounded path duality of relational structures.Logical Methods in Computer Science, 1(1), 2005

    work page 2005

  50. [50]

    Dalmau and J

    V. Dalmau and J. Pearson. Closure functions and width 1 problems. InProceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pages 159–173, 1999

    work page 1999

  51. [51]

    Dechter.Constraint Processing

    R. Dechter.Constraint Processing. Morgan Kaufmann, 2003

    work page 2003

  52. [52]

    Wiley, 2004

    Dummit and Foote.Abstract Algebra. Wiley, 2004. Third edition

    work page 2004

  53. [53]

    L. Egri, B. Larose, and P. Tesson. Symmetric Datalog and constraint satisfaction problems in logspace. InProceedings of the Symposium on Logic in Computer Science (LICS), pages 193–202, 2007

    work page 2007

  54. [54]

    M. M. El-Zahar and N. Sauer. The chromatic number of the product of two 4-chromatic graphs is 4.Combinatorica, 5(2):121–126, 1985

    work page 1985

  55. [55]

    T. Feder. Classification of homomorphisms to oriented cycles and ofk-partite satisfia- bility.SIAM Journal on Discrete Mathematics, 14(4):471–480, 2001. 202

    work page 2001

  56. [56]

    Feder and M

    T. Feder and M. Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the Symposium on Theory of Computing (STOC), pages 612 – 622, 1993

    work page 1993

  57. [57]

    Feder and M

    T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.SIAM Journal on Computing, 28(1):57–104, 1999

    work page 1999

  58. [58]

    Garey and D

    M. Garey and D. Johnson.A guide to NP-completeness. CSLI Press, Stanford, 1978

    work page 1978

  59. [59]

    D. Geiger. Closed systems of functions and predicates.Pacific Journal of Mathematics, 27:95–100, 1968

    work page 1968

  60. [60]

    Goldmann and A

    M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Information and Computation, 178(1):253–262, 2002

    work page 2002

  61. [61]

    G. H. Hardy and E. M. Wright.An introduction to the theory of numbers. Oxford University Press, 2008. Sixth edition

    work page 2008

  62. [62]

    Hell and J

    P. Hell and J. Neˇ setˇ ril. On the complexity of H-coloring.Journal of Combinatorial Theory, Series B, 48:92–110, 1990

    work page 1990

  63. [63]

    Hell and J

    P. Hell and J. Neˇ setˇ ril. The core of a graph.Discrete Mathematics, 109:117–126, 1992

    work page 1992

  64. [64]

    Hell and J

    P. Hell and J. Neˇ setˇ ril.Graphs and Homomorphisms. Oxford University Press, Oxford, 2004

    work page 2004

  65. [65]

    Hobby and R

    D. Hobby and R. McKenzie.The structure of finite algebras, volume 76 ofContemporary Mathematics. American Mathematical Society, 1988

    work page 1988

  66. [66]

    Hodges.Model theory

    W. Hodges.Model theory. Cambridge University Press, Cambridge, 1993

    work page 1993

  67. [67]

    Hodges.A shorter model theory

    W. Hodges.A shorter model theory. Cambridge University Press, Cambridge, 1997

    work page 1997

  68. [68]

    Janson, T

    S. Janson, T. Luczak, and A. Rucinski.Random Graphs. John Wiley and Sons, New York, 2000

    work page 2000

  69. [69]

    Jeavons, D

    P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints.Journal of the ACM, 44(4):527–548, 1997

    work page 1997

  70. [70]

    Jovanovi´ c, P

    J. Jovanovi´ c, P. Markovi´ c, R. McKenzie, and M. Moore. Optimal strong Mal’cev con- ditions for congruence meet-semidistributivity in locally finite varieties.Algebra Uni- versalis, 76:305–325, 2016

    work page 2016

  71. [71]

    A. Kazda. Maltsev digraphs have a majority polymorphism.European Journal of Combinatorics, 32:390–397, 2011

    work page 2011

  72. [72]

    K. A. Kearnes, P. Markovi´ c, and R. McKenzie. Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties.Algebra Universalis, 72(1):91–100, 2015

    work page 2015

  73. [73]

    Kolmogorov, A

    V. Kolmogorov, A. A. Krokhin, and M. Rol´ ınek. The complexity of general-valued CSPs.SIAM J. Comput., 46(3):1087–1110, 2017

    work page 2017

  74. [74]

    Kolmogorov, J

    V. Kolmogorov, J. Thapper, and S. ˇZivn´ y. The power of linear programming for general- valued CSPs.SIAM J. Comput., 44(1):1–36, 2015. 203

    work page 2015

  75. [75]

    M. Kozik. Weak consistency notions for all the CSPs of bounded width. InProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, New York, NY, USA, July 5-8, 2016, pages 633–641, 2016

    work page 2016

  76. [76]

    M. Kozik. Solving CSPs using weak local consistency.SIAM J. Comput., 50(4):1263– 1286, 2021

    work page 2021

  77. [77]

    Kozik, A

    M. Kozik, A. Krokhin, M. Valeriote, and R. Willard. Characterizations of several Maltsev conditions.Algebra universalis, 73(3):205–224, 2015

    work page 2015

  78. [78]

    Kozik and J

    M. Kozik and J. Ochremiak. Algebraic properties of valued constraint satisfaction problem. InAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 846–858, 2015

    work page 2015

  79. [79]

    Kun and M

    G. Kun and M. Szegedy. A new line of attack on the dichotomy conjecture.Eur. J. Comb., 52:338–367, 2016

    work page 2016

  80. [80]

    Larose, C

    B. Larose, C. Loten, and C. Tardif. A characterisation of first-order constraint satisfac- tion problems.Logical Methods in Computer Science, 3(4:6), 2007

    work page 2007

Showing first 80 references.