Quantified constraint satisfaction problem on semicomplete digraphs

DOI10.1145/3007899MaRDI QIDQ5278200zbMATH OpenOpenAlexWikidataFDO

Authors Petar Marković, Barnaby Martin, Petar Dapić

Publication date 13 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/20046/1/20046.pdf

zbMATH Keywords

complexitypolymorphismquantified constraintssemicomplete digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• QCSP on semicomplete digraphs
• Principles and Practice of Constraint Programming – CP 2004
• STACS 2005
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• Quantified constraint satisfaction and the polynomially generated powers property

Cites work

• scientific article; zbMATH DE number 3679856 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 5030273 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Duality and Polynomial Testing of Tree Homomorphisms
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP
• Logical Approaches to Computational Barriers
• Maltsev digraphs have a majority polymorphism
• Meditations on quantified constraint satisfaction
• On Maltsev digraphs
• On the complexity of H-coloring
• QCSP on partially reflexive cycles -- the wavy line of tractability
• Quantified Equality Constraints
• Relatively quantified constraint satisfaction
• Retractions to Pseudoforests
• 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 Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of constraint satisfaction games and QCSP
• The complexity of satisfiability problems
• The lattice of all clones of self-dual functions in three-valued logic
• The structure of finite algebras

Cited in

(11)

• The number of clones determined by disjunctions of unary relations
• Quantified constraint satisfaction and the polynomially generated powers property
• Principles and Practice of Constraint Programming – CP 2004
• Constraint satisfaction with counting quantifiers
• QCSP on partially reflexive cycles -- the wavy line of tractability
• QCSP on partially reflexive forests
• Low-level dichotomy for quantified constraint satisfaction problems
• QCSP on semicomplete digraphs
• The complexity of quantified constraints using the algebraic formulation
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP

This page was built for publication: Quantified constraint satisfaction problem on semicomplete digraphs

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