Beyond Boolean surjective VCSPs

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

Authors Gregor Matl, S. Zivny

Publication date 18 July 2022

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 Polynomial Algorithm for the k-cut Problem for Fixed k
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• 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 Multiterminal Cuts
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of general-valued CSPs
• The complexity of global cardinality constraints
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The complexity of surjective homomorphism problems-a survey
• 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)