Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

Abstract

The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Maróti) in an elementary and self-contained way.

Cited by in corpus (30)

• Algebraic approach to promise constraint satisfaction
• The weakest nontrivial idempotent equations
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• A finer reduction of constraint problems to digraphs
• A Dichotomy for First-Order Reducts of Unary Structures
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Axiomatisability and hardness for universal Horn classes of hypergraphs
• Pseudo-loop conditions
• Strong subalgebras and the Constraint Satisfaction Problem
• Promises Make Finite (Constraint Satisfaction) Problems Infinitary
• Local structure of idempotent algebras II
• Examples, counterexamples, and structure in bounded width algebras
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Finitely (In)tractable Promise Constraint Satisfaction Problems
• Small Promise CSPs that reduce to large CSPs
• Graphs of relational structures: restricted types
• Taylor term does not imply any nontrivial linear one-equality Maltsev condition
• Injective hardness condition for PCSPs
• Galois theory for semiclones
• A Constraint Satisfaction Problem Algorithm for Certain 2-Semilattice-over-Edge Algebras
• Deciding the existence of quasi weak near unanimity terms in finite algebras
• The number of clones determined by disjunctions of unary relations
• Chromatic numbers of directed hypergraphs with no "bad" cycles
• Symmetric Operations on Domains of Size at Most 4
• The minimal arity of near-unanimity polymorphisms
• Universal Algebraic Methods for Constraint Satisfaction Problems
• A dichotomy theorem for nonuniform CSPs simplified
• On absorption in semigroups and $n$-ary semigroups
• On the complexity of $\mathbb{H}$-coloring for special oriented trees
• The Smallest Hard Trees