Beyond Boolean surjective VCSPs

DOI10.4230/LIPICS.STACS.2019.52MaRDI QIDQ5090503zbMATH OpenFDO

Authors Gregor Matl, S. Zivny

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2019.52

zbMATH Keywords

constraint satisfaction problemsgraph cutssurjective constraint satisfactionvalued constraint satisfaction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of conservative valued CSPs

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Algebraic properties of valued constraint satisfaction problem
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Colouring, constraint satisfaction, and complexity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On generating all solutions of generalized satisfiability problems
• On the complexity of H-coloring
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of general-valued CSPs
• The complexity of global cardinality constraints
• The Complexity of Multiterminal Cuts
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The complexity of surjective homomorphism problems-a survey
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The power of linear programming for general-valued CSPs
• Towards minimizing k-submodular functions

Cited in

(1)

• Minimum violation vertex maps and their applications to cut problems

This page was built for publication: Beyond Boolean surjective VCSPs

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