The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
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
Cited in
(only showing first 100 items - show all)- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Topological Birkhoff
- The complexity of weighted Boolean \#CSP with mixed signs
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Homomorphisms of sparse signed graphs
- Tractability in constraint satisfaction problems: a survey
- scientific article; zbMATH DE number 7471701 (Why is no real title available?)
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Maximal infinite-valued constraint languages
- On the complexity of the model checking problem
- A Logical Approach to Constraint Satisfaction
- Tractable structures for constraint satisfaction with truth tables
- List-homomorphism problems on graphs and arc consistency
- Relatively quantified constraint satisfaction
- Equivariant algorithms for constraint satisfaction problems over coset templates
- Reconfiguration of homomorphisms to reflexive digraph cycles
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- An approximation trichotomy for Boolean \#CSP
- Computing hypergraph width measures exactly
- Enumerating homomorphisms
- The existence of a near-unanimity term in a finite algebra is decidable
- Computing vertex-surjective homomorphisms to partially reflexive trees
- The complexity of surjective homomorphism problems-a survey
- \(H\)-coloring dichotomy revisited
- Hard constraint satisfaction problems have hard gaps at location 1
- Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
- The complexity of counting homomorphisms seen from the other side
- Finding Reductions Automatically
- The complexity of approximately counting tree homomorphisms
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- Constraint satisfaction with succinctly specified relations
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- The complexity of partition functions
- Graph partitions with prescribed patterns
- Testing list \(H\)-homomorphisms
- Constraint satisfaction problems over numeric domains
- The complexity of constraint satisfaction games and QCSP
- Backdoors into heterogeneous classes of SAT and CSP
- Constraint satisfaction, irredundant axiomatisability and continuous colouring
- Constraint satisfaction problems over the integers with successor
- Adjusted interval digraphs
- Obstructions to partitions of chordal graphs
- View-based query processing: on the relationship between rewriting, answering and losslessness
- Colouring, constraint satisfaction, and complexity
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- Conjunctive-query containment and constraint satisfaction
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Regular families of forests, antichains and duality pairs of relational structures
- Digraph matrix partitions and trigraph homomorphisms
- scientific article; zbMATH DE number 7378350 (Why is no real title available?)
- Bounded Tree-Width and CSP-Related Problems
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Conservative constraint satisfaction re-revisited
- Majority constraints have bounded pathwidth duality
- The complexity of the list homomorphism problem for graphs
- Non-dichotomies in Constraint Satisfaction Complexity
- Reflexive digraphs with near unanimity polymorphisms
- Recent Results on the Algebraic Approach to the CSP
- The complexity of soft constraint satisfaction
- On digraph coloring problems and treewidth duality
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Residual properties of simple graphs
- Affine systems of equations and counting infinitary logic
- Universal algebra and hardness results for constraint satisfaction problems
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Dualities for Constraint Satisfaction Problems
- The constraint satisfaction problem and universal algebra
- Varieties with few subalgebras of powers
- A dichotomy for real weighted Holant problems
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Hybrid tractability of valued constraint problems
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- The existence of a near-unanimity function is decidable
- Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- Colourings, homomorphisms, and partitions of transitive digraphs
- Uniform Constraint Satisfaction Problems and Database Theory
- The complexity of general-valued CSPs
- Maltsev digraphs have a majority polymorphism
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Combinatorial problems raised from 2-semilattices
- Term equation satisfiability over finite algebras
- A new tractable class of constraint satisfaction problems
- Binary constraint satisfaction problems defined by excluded topological minors
- A complete dichotomy rises from the capture of vanishing signatures
- Computational complexity of auditing finite attributes in statistical databases
- Tropically convex constraint satisfaction
- CSP dichotomy for special polyads
- Complexity of correspondence \(H\)-colourings
- The power of Sherali-Adams relaxations for general-valued CSPs
- A Galois connection for valued constraint languages of infinite size
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Absorption in universal algebra and CSP
- Algebra and the complexity of digraph CSPs: a survey
- A surprising permanence of old motivations (a not-so-rigid story)
- Peek arc consistency
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)
