Source-linked AI summary
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
Libor Barto, Marcin Kozik
TL;DR
The paper addresses the Algebraic Dichotomy Conjecture, which classifies fixed-template CSPs through the Taylor-variety status of their polymorphism algebras. It introduces absorbing-subalgebra and cyclic-term characterizations of finitely generated Taylor varieties, using them to obtain elementary, self-contained proofs of several central results. The paper also identifies a deep connection between CSP tools and universal algebra.
Problem
The Algebraic Dichotomy Conjecture requires a usable characterization of Taylor varieties to establish polynomial-time solvability for the corresponding CSPs, but existing characterizations can be difficult or algebraically deep.
Method
The paper develops two characterizations of finitely generated Taylor varieties, one based on absorbing subalgebras and one based on cyclic terms.
Results
The characterizations support elementary, self-contained proofs of the Bang-Jensen–Hell conjecture and the weak near-unanimity characterization of locally finite Taylor varieties.
Takeaways & Limitations
The results provide new tools for the Algebraic Dichotomy Conjecture and indicate a deep connection between CSP methods and universal algebra.
Takeaways & Limitations
The characterizations discussed here require finitely generated Taylor varieties; this assumption cannot be relaxed to locally finite varieties.
Abstract
from arXiv · showhide
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.
Introduction
The paper addresses the Algebraic Dichotomy Conjecture by introducing two new characterizations of finitely generated Taylor varieties. These characterizations support elementary, self-contained proofs of several CSP and universal-algebra results.
- The Constraint Satisfaction Problem asks whether variables can be assigned values satisfying all imposed constraints and provides a common framework for theoretical and real-life applications.
- The Algebraic Dichotomy Conjecture proposes that each fixed-template CSP is either solvable in polynomial time or NP-complete, with the classification determined by whether its associated algebra lies in a Taylor variety.
- Proving the conjecture requires workable equivalent conditions for Taylor varieties because Taylor’s original characterization is difficult to use algorithmically.
- The paper provides two new conditions for finitely generated Taylor varieties, using absorbing subalgebras and cyclic terms.
- The new characterizations yield elementary, self-contained proofs of the Bang-Jensen–Hell conjecture and other previously established results without heavy algebraic machinery.
- The results also indicate a deep connection between tools developed for CSP and questions in universal algebra.
1. Preliminaries
The preliminaries introduce the algebraic and relational structures used throughout the paper, including varieties, terms, Taylor conditions, and the homomorphism formulation of CSP. They also state foundational characterizations linking Taylor varieties and CSP complexity.
- Algebras and varieties: An algebra is a set equipped with finitary operations, while a variety is a class closed under isomorphic copies, subalgebras, factoralgebras, and products.
- Terms and operations: The paper defines term operations and introduces the composition operation t1 ∗ t2, which combines a k-ary term with an l-ary term into a kl-ary term.
- Algebras and varieties: A finitely generated variety is generated by finitely many finite algebras and is therefore locally finite.
- Taylor varieties: A cyclic term is an idempotent term invariant under cyclic permutation of its arguments, whereas a weak near-unanimity term equates all placements of one exceptional argument.
- Taylor varieties: Taylor varieties are characterized by the absence of a two-element algebra whose every term operation is a projection, while locally finite Taylor varieties are equivalently characterized by weak near-unanimity terms.
- Constraint Satisfaction Problems: For a fixed relational structure A, CSP(A) asks whether an input structure maps homomorphically to A, and the Feder–Vardi conjecture predicts polynomial-time solvability or NP-completeness.
- Algebraic approach to CSP: For a core template, the algebra of idempotent polymorphisms fully determines the computational complexity of its CSP.
2. Absorbing subalgebras and absorption theorem
This section introduces absorbing subalgebras and develops the Absorption Theorem, whose proof is self-contained and elementary. It establishes structural consequences that characterize Taylor varieties through linked subalgebras and absorbing subuniverses.
- Definitions: An absorbing subalgebra B of A is closed under a term operation whenever all but at most one input lies in B.B absorbs A when such a term operation exists; proper absorbing subalgebras are nonempty proper subalgebras.
- Basic properties: Absorption is transitive and closed under intersections of absorbing subalgebras.If C absorbs B and B absorbs A, then C absorbs A; if B and C absorb A, then B ∩ C absorbs A.
- Proof framework: The proof uses neighborhood operations on subalgebras of a product, showing that these operations preserve subalgebra and absorption structure.For X ≤ A and Y ≤ B, the corresponding neighborhoods X+ and Y− are subalgebras; under absorption hypotheses they remain absorbing.
- Taylor-term consequences: A finite Taylor algebra without a proper absorbing subalgebra admits a term operation that can realize any target while fixing any chosen coordinate to any prescribed element.A common term with this property exists for two finite Taylor algebras, and more generally for any finite number of them.
- Absorption Theorem: The Absorption Theorem states that a proper, subdirect, linked subalgebra R of A × B forces a proper absorbing subalgebra in A or B.This is the central structural result for finite algebras in a Taylor variety.
- Absorption Theorem: For finite algebras in a Taylor variety, linked subalgebras and absorbing subuniverses satisfy closure, restriction, and product-intersection properties.These include preservation of linkedness under absorption and the existence of compatible absorbing subuniverses on both factors.
3. New proof of the Smooth Theorem
The section gives an elementary proof of the Smooth Theorem using algebraic properties of smooth digraphs, absorbing subalgebras, and Taylor polymorphisms. The proof reduces the theorem to showing that suitable algebraic-length-one digraphs contain loops.
- The Smooth Theorem: The Smooth Theorem classifies CSP(H) as polynomial-time decidable when every core component is a circle, and NP-complete otherwise.This is the classification being reproved in the section.
- Reduction: The proof reduces the polynomial-time part to showing that every smooth digraph with a Taylor polymorphism retracts onto a disjoint union of circles.The reduction uses the equivalence of CSPs for a relational structure and its core.
- Loop theorem: The central algebraic step states that a smooth digraph of algebraic length one with a Taylor polymorphism contains a loop.The stronger version also places the loop in an absorbing subuniverse when an appropriate absorbing subuniverse exists.
- Inductive proof: The induction maintains weak connectivity and algebraic length one while passing to smooth parts and smaller induced digraphs.The proof proceeds by induction on the size of the vertex set and uses claims about the sets generated by paths and fences.
- Component structure: For a weak component of algebraic length one, the proof constructs a vertex whose path image contains a cycle and a fence whose image covers the component.These constructions support the later extraction of a nonempty smooth part with algebraic length one.
4. Cyclic terms in Taylor varieties
The paper characterizes finitely generated Taylor varieties through cyclic terms, showing that Taylor-ness is equivalent to possessing cyclic terms, including one of every prime arity exceeding the algebra’s size. These results support consequences for CSP complexity and recover weak near-unanimity and graph dichotomies.
- Main characterization: Taylor varieties generated by a finite algebra are exactly those possessing a cyclic term.The equivalence also holds for the algebra generating the variety.
- Prime arities: A finite algebra in a Taylor variety has a p-ary cyclic term for every prime p greater than its size.This theorem supplies the prime-arity condition used in the CSP restatement.
- Cyclic relations: For finite idempotent algebras, having a k-ary cyclic term is equivalent to every nonempty cyclic subalgebra of A^k containing a constant tuple.The proof uses cyclic shifts and coordinatewise application of the term.
- CSP consequences: The paper applies the characterization to restate the Algebraic Dichotomy Conjecture: the CSP is polynomial-time solvable when every relevant cyclic relation has a constant tuple, and NP-complete otherwise.The relations are nonempty positively primitively defined cyclic p-ary relations, with p prime and larger than the template universe.
- CSP consequences: The same framework reproves the bipartite-versus-nonbipartite dichotomy for loopless undirected graphs.Bipartite graphs yield polynomial-time solvable CSPs, whereas nonbipartite graphs yield NP-complete CSPs.
- Further consequences: The cyclic-term characterization implies that locally finite idempotent varieties are Taylor exactly when they have a weak near-unanimity term.The paper presents this as a consequence of the main theorem.