The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

DOI10.1137/S0097539794266766zbMATH Open0914.68075OpenAlexW2150339067WikidataQ56389117 ScholiaQ56389117MaRDI QIDQ4210136FDOQ4210136

Authors: Moshe Y. Vardi, Tomás Feder 

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794266766

Recommendations

• A Dichotomy Theorem for Typed Constraint Satisfaction Problems
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1670830
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A proof of the CSP dichotomy conjecture

zbMATH Keywords

graph coloringgroup theorylinear equationssatisfiabilityDatalog

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (only showing first 100 items - show all)

• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Proof Complexity Meets Algebra
• Uniform and nonuniform recognizability.
• CSP dichotomy for special polyads
• Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
• Join colourings of chordal graphs
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Dismantlability, connectedness, and mixing in relational structures
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• High girth hypergraphs with unavoidable monochromatic or rainbow edges
• The quantum monad on relational structures
• Quasi-transitive digraphs and their extensions
• On the Complexity of Holant Problems
• Semilattice polymorphisms and chordal graphs
• Surjective \(H\)-colouring: new hardness results
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Homomorphism reconfiguration via homotopy
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Computational complexity of various Mal'cev conditions
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Parameterized counting of partially injective homomorphisms
• Why is it hard to obtain a dichotomy for consistent query answering?
• A dichotomy for first-order reducts of unary structures
• From \(A\) to \(B\) to \(Z\)
• Permutation groups with small orbit growth
• Binarisation for valued constraint satisfaction problems
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Counting List Matrix Partitions of Graphs
• Galois connections for patterns: an algebra of labelled graphs
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• Dichotomy for tree-structured trigraph list homomorphism problems
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• The Complexity of Counting Quantifiers on Equality Languages
• Tractable combinations of theories via sampling
• Quantified constraint satisfaction problem on semicomplete digraphs
• NP for Combinatorialists
• On tree-preserving constraints
• The wonderland of reflections
• Emptiness problems for distributed automata
• First-Order Model Checking Problems Parameterized by the Model
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• The complexity of quantified constraints using the algebraic formulation
• Correspondence homomorphisms to reflexive graphs
• On the CSP Dichotomy Conjecture
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Commutative idempotent groupoids and the constraint satisfaction problem.
• Constraint satisfaction problems for reducts of homogeneous graphs
• On rainbow-free colourings of uniform hypergraphs
• Polyadic sets and homomorphism counting
• ASNP: a tame fragment of existential second-order logic
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• List-homomorphism problems on graphs and arc consistency
• Residual properties of simple graphs
• Distance constraint satisfaction problems
• A dichotomy for real weighted Holant problems
• A Logical Approach to Constraint Satisfaction
• Graph partitions with prescribed patterns
• The complexity of surjective homomorphism problems-a survey
• Title not available (Why is that?)
• Recent Results on the Algebraic Approach to the CSP
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Tractability in constraint satisfaction problems: a survey
• Enumerating homomorphisms
• Colouring, constraint satisfaction, and complexity
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Dualities for Constraint Satisfaction Problems
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Uniform Constraint Satisfaction Problems and Database Theory
• The complexity of weighted Boolean \#CSP with mixed signs
• Tractable structures for constraint satisfaction with truth tables
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Hybrid tractability of valued constraint problems
• The complexity of counting homomorphisms seen from the other side
• Backdoors into heterogeneous classes of SAT and CSP
• View-based query processing: on the relationship between rewriting, answering and losslessness
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• Conservative constraint satisfaction re-revisited
• Maximal infinite-valued constraint languages
• Relatively quantified constraint satisfaction
• An approximation trichotomy for Boolean \#CSP
• Computing hypergraph width measures exactly
• On the complexity of the model checking problem
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Constraint satisfaction problems over the integers with successor
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• Conjunctive-query containment and constraint satisfaction
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• A new tractable class of constraint satisfaction problems
• Majority constraints have bounded pathwidth duality
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• The complexity of general-valued CSPs

Uses Software

• Datalog

This page was built for publication: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

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