Min CSP on four elements: moving beyond submodularity

DOI10.1007/978-3-642-23786-7_34MaRDI QIDQ3169450zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Fredrik Kuivinen, Johan Thapper

Publication date 23 September 2011

Published in Principles and Practice of Constraint Programming – CP 2011 (Search for Journal in Brave)

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

zbMATH Keywords

bisubmodularitycombinatorial optimisationcomputational complexityconstraint satisfaction problemssubmodularity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly well-understood. However, there is yet no characterisation of VCSPs that can be solved exactly in polynomial time. This is unsatisfactory, since such results are interesting from a combinatorial optimisation perspective; there are deep connections with, for instance, submodular and bisubmodular minimisation. We consider the Min and Max CSP problems (i.e. where the cost functions only attain values in {0,1}) over four-element domains and identify all tractable fragments. Similar classifications were previously known for two- and three-element domains. In the process, we introduce a new class of tractable VCSPs based on a generalisation of submodularity. We also extend and modify a graph-based technique by Kolmogorov and Zivny (originally introduced by Takhanov) for efficiently obtaining hardness results in our setting. This allow us to prove the result without relying on computer-assisted case analyses (which otherwise are fairly common when studying the complexity and approximability of VCSPs.) The hardness results are further simplified by the introduction of powerful reduction techniques.

Recommendations

• The complexity of conservative valued CSPs
• The complexity of conservative valued CSPs
• Skew bisubmodularity and valued CSPs

Cited in

(13)

• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Half-integrality, LP-branching, and FPT algorithms
• Skew bisubmodularity and valued CSPs
• A submodular-based decomposition strategy for valued CSPs
• A tractable class of binary VCSPs via M-convex intersection
• The complexity of valued CSPs
• Submodular functions and valued constraint satisfaction problems over infinite domains
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• Skew bisubmodularity and valued CSPs
• The complexity of conservative valued CSPs
• Classes of submodular constraints expressible by graph cuts

This page was built for publication: Min CSP on four elements: moving beyond submodularity

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