Algebraic global gadgetry for surjective constraint satisfaction

DOI10.1007/S00037-024-00253-4MaRDI QIDQ6581872zbMATH OpenFDO

Authors Hubie Chen

Publication date 1 August 2024

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

constraint satisfactionuniversal algebra

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Recommendations

• An algebraic hardness criterion for surjective constraint satisfaction.
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1670830
• Universal algebra and hardness results for constraint satisfaction problems
• On the reduction of the CSP dichotomy conjecture to digraphs

Cites work

• scientific article; zbMATH DE number 786134 (Why is no real title available?)
• A dichotomy theorem for the inverse satisfiability problem
• A proof of the CSP dichotomy conjecture
• An algebraic hardness criterion for surjective constraint satisfaction.
• Asking the Metaquestions in Constraint Tractability
• Best-case and worst-case sparsifiability of Boolean CSPs
• Coloring mixed hypertrees
• Complexity classifications of Boolean constraint satisfaction problems
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Homomorphisms are a good basis for counting small subgraphs
• Large networks and graph limits
• Operations with structures
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Strong partial clones and the time complexity of SAT problems
• Surjective H-Colouring over Reflexive Digraphs
• Surjective \(H\)-colouring: new hardness results
• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Rooted Phylogeny Problems
• The Exponential Time complexity of counting (quantum) graph homomorphisms
• The algebras of partial functions and their invariants
• The complexity of counting surjective homomorphisms and compactions
• The complexity of global cardinality constraints
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Tractable cases of the extended global cardinality constraint

This page was built for publication: Algebraic global gadgetry for surjective constraint satisfaction

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