The Structure of Finite Algebras and the Constraint Satisfaction Problem (17rit685)

Arriving in Banff, Alberta Sunday, August 6 and departing Sunday August 13, 2017


(Jagiellonian University)

(Simon Fraser University)


All the three approaches mentioned above have led to surprisingly similar results, such as the Rectangularity Lemma, which in different cases states the same result for quite different structural features of algebras. The first two approaches also allowed to prove, although in very different ways the dichotomy for conservative CSPs [3,4] and to obtain a characterization of CSPs of bounded width. The approach through key relations has been quite successful in proving the Dichotomy Conjecture for small relational structures, up to 7 elements. Clearly, such similarities are not likely to be coincidental, and probably are manifestations of a deeper and more general phenomenon. The goal of this proposal is bring together the inventors of all 3 approaches to try to identify the general principle behind them.

More specifically, we plan to (1) Find the connection between the main building blocks of the 3 approaches: as-components, absorbing subuniverse, and blocks of key relations. Ideally, we would like to prove a more general structural result unifying the three constructs. (2) Express in a more general way the structural properties of relations playing the central role in the 3 approaches: absorption, quasi-decomposition, etc. (3) Try to combine the three approaches to advance the study of the Dichotomy Conjecture. Although we don't dare to propose to settle a problem that has been open for 40 years within a week, we hope to make a partial progress in this direction.

If we have an opportunity we would also like to explore another topic closely related to the structural theory of the CSP. One of the major classes of CSP algorithms is propagation algorithms. A propagation algorithm attempts to consider a fairly small part of the problem, solve it, and then propagates the solution(s) in order to modify the entire problem. If such an algorithm considers fragments of CSPs of constant size, it is also called a local consistency algorithm. Algorithms of this type are responsible for solving CSPs of bounded width. More complex propagation algorithms are often needed to solve other types of CSPs.

Recently it has been realized [18,19] that algorithms working for CSPs have very much in common with algorithms for the Graph Isomorphism problem, the notorious problem that resists complexity classification. Most of Graph Isomorphism algorithms including the recent breakthrough quasi-polynomial algorithm by Babai [20] combine techniques very similar to local consistency algorithms with algorithms not dissimilar to the CSP algorithm for problems with small solution space. One of the techniques of the first type is Weisfeiler-Leman colour coding algorithm that even admits a hierarchy similar to that of CSP local consistency algorithms. Algorithms of the second type are based on the structure of the automorphism group of the graph. Recently Dawar et al. [19] suggested more powerful propagation algorithms for Graph Isomorphism that use linear maps rather than simple color coding. We would like to investigate further the connections between the two problems and algorithmic approaches to them.

Justification. Although we often meet at conferences in different combinations, so far we haven't had a chance to stay in one place and concentrate on a problem of common interest. BIRS would be an ideal place for that. Note also that up to now we have had no joint papers, except Barto and Kozik working closely to gather and Bulatov and Kozik coauthored a paper unrelated with this project.

Scheduling. Due to various teaching and other commitments and travel plans, the best week for us would be the second week of August (starting Aug 6). The second best is the second week of July (starting Jul 9). The first and third weeks of July and August are possible although some will have to depart earlier. We cannot make it before July and after August, also the weeks Jul 23-29 and August 20-26 are not possible.


[1] Thomas J. Schaefer: The Complexity of Satisfiability Problems. STOC 1978: 216-226

[2] Tom.s Feder, Moshe Y. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput. 28(1): 57-104 (1998)

[3] Andrei A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1): 66-120 (2006)

[4] Andrei A. Bulatov: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12(4): 24 (2011)

[5] Libor Barto: The Dichotomy for Conservative Constraint Satisfaction Problems Revisited. LICS 2011: 301-310

[6] Andrei A. Bulatov, VÌctor Dalmau: A Simple Algorithm for Mal'tsev Constraints. SIAM J. Comput. 36(1): 16-27 (2006)

[7] Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, Ross Willard: Tractability and Learnability Arising from Algebras with Few Subpowers. SIAM J. Comput. 39(7): 3023-3037 (2010)

[8] Libor Barto, Marcin Kozik: Constraint Satisfaction Problems Solvable by Local Consistency Methods. J. ACM 61(1): 3:1-3:19 (2014)

[9] Andrei A. Bulatov: Graphs of relational structures: restricted types. LICS 2016: 642-651

[10] Marcin Kozik: Weak consistency notions for all the CSPs of bounded width. LICS 2016: 633-641

[11] Peter Jeavons, David A. Cohen, Marc Gyssens: Closure properties of constraints. J. ACM 44(4): 527-548 (1997)

[12] Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin: Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34(3): 720-742 (2005)

[13] Andrei A. Bulatov: A Graph of a Relational Structure and Constraint Satisfaction Problems. LICS 2004: 448-457

[14] Andrei A. Bulatov: Graphs of finite algebras, edges, and connectivity. CoRR abs/1601.07403 (2016)

[15] Libor Barto, Marcin Kozik: Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem. Logical Methods in Computer Science 8(1) (2012)

[16] Libor Barto: Constraint satisfaction problem and universal algebra. SIGLOG News 1(2): 14-24 (2014)

[17] Dmitriy Zhuk: Key (critical) relations preserved by a weak near-unanimity function. arXiv:1501.04597 (2015)

[18] Christoph Berkholz, Martin Grohe: Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. CoRR abs/1607.04287 (2016)

[19] Jannis Bulian, Anuj Dawar: Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree. Algorithmica 75(2): 363-382 (2016)

[20] Laszlo Babai: Graph isomorphism in quasipolynomial time [extended abstract]. STOC 2016: 684-697