The Complexity of Boolean Surjective General-Valued CSPs

DOI10.4230/LIPICS.MFCS.2017.4zbMATH Open1440.68116OpenAlexW2949796101MaRDI QIDQ5111218FDOQ5111218

Peter Fulla, S. Zivny

Publication date: 26 May 2020

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

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
• The complexity of finite-valued CSPs
• The complexity of finite-valued CSPs
• 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

zbMATH Keywords

constraint satisfaction problemspolymorphismsvalued CSPMin-Cutmultimorphismssurjective CSP

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• An algebraic hardness criterion for surjective constraint satisfaction.

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)