Complexity and polymorphisms for digraph constraint problems under some basic constructions

DOI10.1142/S0218196716500600MaRDI QIDQ5298320zbMATH OpenOpenAlexFDO

Authors Marcel Jackson, Tomasz Kowalski, Todd Niven

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

constraint satisfaction problemdirected graphhomomorphism problemone point extensionpolymorphism

Mathematics Subject Classification ID

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

Abstract: The role of polymorphisms in determining the complexity of constraint satisfaction problems is well established. In this context we study the stability of CSP complexity and polymorphism properties under some basic graph theoretic constructions. As applications we observe a collapse in the applicability of algorithms for CSPs over directed graphs with both a total source and a total sink: the corresponding CSP is solvable by the "few subpowers algorithm" if and only if it is solvable by a local consistency check algorithm. Moreover, we find that the property of "strict width" and solvability by few subpowers are unstable under first order reductions. The analysis also yields a complete characterisation of the main polymorphism properties for digraphs whose symmetric closure is a complete graph.

Recommendations

• Polymorphisms of small digraphs
• A finer reduction of constraint problems to digraphs
• On the reduction of the CSP dichotomy conjecture to digraphs
• Asking the Metaquestions in Constraint Tractability
• Algebra and the complexity of digraph CSPs: a survey

Cites work

• A Characterisation of First-Order Constraint Satisfaction Problems
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Algebras Whose Congruence Lattices are Distributive.
• Classifying the Complexity of Constraints Using Finite Algebras
• Constraint Satisfaction Problems of Bounded Width
• Distributivity and Permutability of Congruence Relations in Equational Classes of Algebras
• Finitely related algebras in congruence modular varieties have few subpowers
• scientific article; zbMATH DE number 176518 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Maltsev digraphs have a majority polymorphism
• The Complexity of Colouring by Semicomplete Digraphs
• The complexity of satisfiability problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The shape of congruence lattices
• The structure of finite algebras
• Tractability and learnability arising from algebras with few subpowers
• Universal algebra and hardness results for constraint satisfaction problems
• Universal algebra. Fundamentals and selected topics
• Varieties with few subalgebras of powers
• Weak near-unanimity functions and digraph homomorphism problems

Cited in

(8)

• Axiomatisability and hardness for universal Horn classes of hypergraphs
• The Gumm level equals the Alvin level in congruence distributive varieties
• Polymorphisms of small digraphs
• A finer reduction of constraint problems to digraphs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Algebra and the complexity of digraph CSPs: a survey
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Maximal digraphs with respect to primitive positive constructability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5298320)