Polymorphisms of small digraphs

MaRDI QIDQ2853188zbMATH OpenFDO

Authors Libor Barto, David Stanovský

Publication date 18 October 2013

Published in Novi Sad Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

constraint satisfaction problempolymorphisms of digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Relational systems, laws of composition (08A02) Applications of universal algebra in computer science (08A70) Graph theory (including graph drawing) in computer science (68R10)

Review text

Constraint satisfaction problems (CSP) form a rich class of algorithmic problems with applications in many areas of computer science. As abstract problems, CSPs are homomorphism problems for relational structures.NEWLINENEWLINE The authors provide a report on results obtained by computer testing the existence of various types of polymorphisms for small digraphs, since a digraph can be seen as a relational structure with one binary relation. The authors choose to check for polymorphisms important in CSP such as Mal'tsev polymorphism, near-unanimity polymorphisms (up to arity 5), edge polymorphisms (up to arity 5), semilattice polymorphism, and so on. The existence of these polymorphisms is checked for all non-isomorphic digraphs with up to 5 vertices, as well as for some randomly chosen digraphs on 6, 7 and 8 vertices.NEWLINENEWLINE The authors also find a digraph on six vertices such that the complexity of its retraction problem is unknown with current techniques and show that this is the smallest such example.

Recommendations

• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• A finer reduction of constraint problems to digraphs
• Asking the Metaquestions in Constraint Tractability
• On the reduction of the CSP dichotomy conjecture to digraphs
• Algebra and the complexity of digraph CSPs: a survey

Cited in

(9)

• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• On Maltsev digraphs
• On Maltsev 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
• Rigid binary relations on a 4-element domain
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• Maltsev digraphs have a majority polymorphism

This page was built for publication: Polymorphisms of small digraphs

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