The complexity of finite-valued CSPs

DOI10.1145/2974019zbMATH Open1410.68177arXiv1210.2987OpenAlexW2523377094MaRDI QIDQ3177814FDOQ3177814

Authors: Johan Thapper, S. Zivny 

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We study the computational complexity of exact minimisation of rational-valued discrete functions. Let $Gamma$ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, $operatornameVCSP(Gamma)$, is the problem of minimising a function given as a sum of functions from $Gamma$. We establish a dichotomy theorem with respect to exact solvability for all finite-valued constraint languages defined on domains of arbitrary finite size. We show that every constraint language $Gamma$ either admits a binary symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of $operatornameVCSP(Gamma)$ exactly, or $Gamma$ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to $operatornameVCSP(Gamma)$.

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

Recommendations

• The complexity of finite-valued CSPs
• The complexity of general-valued CSPs
• The complexity of conservative valued CSPs
• The power of linear programming for general-valued CSPs
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization

zbMATH Keywords

complexitydichotomydiscrete optimizationvalued constraint satisfaction problemsfinite-valued constraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (60)

• Super-reparametrizations of weighted CSPs: properties and optimization perspective
• Valued constraint satisfaction problems
• CLAP: A New Algorithm for Promise CSPs
• Generalized minimum 0-extension problem and discrete convexity
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Planar Valued CSPs
• A definability dichotomy for finite valued CSPs
• Parameterized algorithms for zero extension and metric labelling problems
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Title not available (Why is that?)
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Tractability in constraint satisfaction problems: a survey
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• The complexity of conservative valued CSPs
• The power of linear programming for general-valued CSPs
• The lattice and semigroup structure of multipermutations
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• Discrete convex functions on graphs and their algorithmic applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of conservative valued CSPs
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Constant-query testability of assignments to constraint satisfaction problems
• Algebraic properties of valued constraint satisfaction problem
• The power of Sherali-Adams relaxations for general-valued CSPs
• The limits of SDP relaxations for general-valued CSPs
• Backdoor sets for CSP
• A tractable class of binary VCSPs via M-convex intersection
• Testing the Complexity of a Valued CSP Language
• Tractability of explaining classifier decisions
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• Hybrid tractable classes of constraint problems
• Sherali-Adams relaxations for valued CSPs
• Necessary conditions for tractability of valued CSPs
• Minimum 0-extension problems on directed metrics
• Skew bisubmodularity and valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• Universal qudit Hamiltonians
• Min CSP on four elements: moving beyond submodularity
• The limits of SDP relaxations for general-valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• A Galois connection for valued constraint languages of infinite size
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Half-integrality, LP-branching, and FPT algorithms
• On planar valued CSPs
• An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains
• The complexity of valued CSPs
• Skew bisubmodularity and valued CSPs
• Minimum violation vertex maps and their applications to cut problems
• The complexity of finite-valued CSPs
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Robust algorithms with polynomial loss for near-unanimity CSPs

This page was built for publication: The complexity of finite-valued CSPs

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