Algebraic global gadgetry for surjective constraint satisfaction
From MaRDI portal
Publication:6581872
DOI10.1007/s00037-024-00253-4zbMath1548.68094MaRDI QIDQ6581872
Publication date: 1 August 2024
Published in: Computational Complexity (Search for Journal in Brave)
Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- Unnamed Item
- Strong partial clones and the time complexity of SAT problems
- The complexity of surjective homomorphism problems-a survey
- An algebraic hardness criterion for surjective constraint satisfaction.
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Best-case and worst-case sparsifiability of Boolean CSPs
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The Exponential Time complexity of counting (quantum) graph homomorphisms
- Tractable cases of the extended global cardinality constraint
- Coloring mixed hypertrees
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The complexity of global cardinality constraints
- The Complexity of Rooted Phylogeny Problems
- The algebras of partial functions and their invariants
- Asking the Metaquestions in Constraint Tractability
- Homomorphisms are a good basis for counting small subgraphs
- Sparsification of SAT and CSP Problems via Tractable Extensions
- A Proof of the CSP Dichotomy Conjecture
- A Dichotomy Theorem for the Inverse Satisfiability Problem
- Surjective H-Colouring over Reflexive Digraphs
- The Complexity of Boolean Surjective General-Valued CSPs
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- The Complexity of Counting Surjective Homomorphisms and Compactions
- Surjective H-colouring: New hardness results
- Operations with structures
This page was built for publication: Algebraic global gadgetry for surjective constraint satisfaction
