The Complexity of Boolean Surjective General-Valued CSPs

DOI10.1145/3282429zbMath1441.68091arXiv1702.04679OpenAlexW2594691059MaRDI QIDQ5205805

Peter Fulla, Stanislav Živný, Hannes Uppman

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.04679

zbMATH Keywords

constraint satisfaction problemspolymorphismsmin-cutvalued CSPmultimorphismssurjective CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (4)

PTAS for Sparse General-valued CSPs ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Unnamed Item

This page was built for publication: The Complexity of Boolean Surjective General-Valued CSPs