Complexity and polymorphisms for digraph constraint problems under some basic constructions

DOI10.1142/S0218196716500600zbMath1401.05132arXiv1304.4986OpenAlexW2963009602MaRDI QIDQ5298320

Marcel Jackson, Todd Niven, Tomasz Kowalski

Publication date: 14 December 2016

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.4986

zbMATH Keywords

polymorphismdirected graphconstraint satisfaction problemone point extensionhomomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40) Directed graphs (digraphs), tournaments (05C20) Automorphisms and endomorphisms of algebraic structures (08A35)

Related Items (5)

Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Unnamed Item ⋮ The Gumm level equals the Alvin level in congruence distributive varieties ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maltsev digraphs have a majority polymorphism
• Universal algebra and hardness results for constraint satisfaction problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Finitely related algebras in congruence modular varieties have few subpowers
• Weak near-unanimity functions and digraph homomorphism problems
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Varieties with few subalgebras of powers
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Complexity of Colouring by Semicomplete Digraphs
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The shape of congruence lattices
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• A Characterisation of First-Order Constraint Satisfaction Problems
• Algebras Whose Congruence Lattices are Distributive.
• Distributivity and Permutability of Congruence Relations in Equational Classes of Algebras

This page was built for publication: Complexity and polymorphisms for digraph constraint problems under some basic constructions