Algebraic global gadgetry for surjective constraint satisfaction

DOI10.1007/S00037-024-00253-4zbMATH Open1548.68094MaRDI QIDQ6581872FDOQ6581872

Authors: Hubie Chen 

Publication date: 1 August 2024

Published in: Computational Complexity (Search for Journal in Brave)

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

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)

Cites Work

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

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)