The Complexity of Boolean Surjective General-Valued CSPs

DOI10.4230/LIPICS.MFCS.2017.4MaRDI QIDQ5111218zbMATH OpenOpenAlexFDO

Authors Peter Fulla, S. Zivny

Publication date 26 May 2020

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2017/8062/

zbMATH Keywords

constraint satisfaction problemsMin-Cutmultimorphismspolymorphismssurjective CSPvalued CSP

Mathematics Subject Classification ID

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

Recommendations

• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of general-valued CSPs
• The complexity of valued CSPs
• On generic NP-completeness of the Boolean satisfiability problem
• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• The complexity of conservative valued CSPs
• The complexity of conservative valued CSPs
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Cites work

• A complete complexity classification of the role assignment problem
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for maximum generalized satisfiability problems.
• A simple min-cut algorithm
• Algebraic properties of valued constraint satisfaction problem
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• An algebraic hardness criterion for surjective constraint satisfaction.
• Classifying the Complexity of Constraints Using Finite Algebras
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Max-Sur-CSP on two elements
• On generating all solutions of generalized satisfiability problems
• Skew bisubmodularity and valued CSPs
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• The Approximability of Three-valued MAX CSP
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of general-valued CSPs
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint satisfaction problem and universal algebra

Cited in

(6)

• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• An algebraic hardness criterion for surjective constraint satisfaction.
• Max-Sur-CSP on two elements
• Beyond Boolean surjective VCSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs

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

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